package kapitel_13

/**
 * Beispiel aus
 *
 * - Algorithmen und Datenstrukturen für Dummies
 *   - von Andreas Gogol-Döring und Thomas Letschert
 *   - Verlag Wiley-VCH; Oktober 2019
 *  - Kapitel 13, Dynamisches Programmieren
 *
 * @author A. Gogol-Döring, Th. Letschert
 */

object AuD_13_09_Fibonacci_App extends App {

  def fibR(n: Int): Long =
    if (n <= 1) n else fibR(n-1) + fibR(n-2)

  def fibTab(n: Int): Long = {
    if (n <= 1) return n
    val Fib: Array[Long] = Array.ofDim(n+1)
    Fib(0) = 0
    Fib(1) = 1
    for (i <- 2 to n)
      Fib(i) = Fib(i-1) + Fib(i-2)
    Fib(n)
  }

  def fib(n: Int): Long = {
    if (n <= 1) return n
    var f1: Long = 0
    var f2: Long = 1
    for (i <- 2 to n) {
      val f = f1 + f2
      f1 = f2
      f2 = f
    }
    f2
  }

  println(fibR(40)) // 102334155
  println(fibTab(50)) // 12586269025
  println(fib(60)) // 1548008755920

}