> For the complete documentation index, see [llms.txt](https://cs-notes.gitbook.io/algorithm-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cs-notes.gitbook.io/algorithm-notes/outline/overview-6/fibonacci-numbers.md).

# Fibonacci Numbers

A mathematical series of numbers as Fibonacci numbers as to provide a foundation for building a [Golden ratio](https://en.wikipedia.org/wiki/Golden_ratio) number, could be computed in a recurrence relation:

Given function *Fn* to denote the nth position of a Fibonacci sequence; And,

*F1* = *F2* = 1; *Fn* = *Fn-1* + *Fn-2*

## A Naive Algorithm

By adopting *top-down* recursive approach,

```


FIBONACCI(n)
  if n ⩽ 2 return 1
  else
    return FIBONACCI(n-1) + FIBONACCI(n-2)

```

which comes down to a recurrence relation: Τ(n) = Τ(n-1) + Τ(n-2) + Ο(1) ⩾ ϕn

Τ(n) ⩾ 2 ⋅ Τ(n-2) + Ο(1) ⩾ 2n/2

Hence, it takes [exponential time](/algorithm-notes/outline/asymptotic-analysis.md) to compute the nth fibonacci number, wherein lots of repetitive computations are being performed; Specifically in the following diagram,

 ![](https://204822229-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LQpLOTVKDY3pIvuIk2h%2F-LW4tonUkNf6RxzF3H-2%2F-LW4tqGOzQLY0PTKzGv_%2Ffibonacci.png?generation=1547361021913604\&alt=media)Figure 1. Fibonacci Numbers in Recursive Computations

To improve upon that, a *memoized* version of such algorithm is introduced:

```


memo := {}
FIBONACCI(n)
  if n in memo
    return memo[n]
  else
    if n ⩽ 2 return 1
    else
      memo[n] := FIBONACCI(n-1) + FIBONACCI(n-2)
      return memo[n]

```

Therefore, FIBONACCI(k) only takes **one** recursion, ∀ k ∈ n; and all memoized calls use Θ(1) time. Thus, the time complexity is Ο(n), space complexity is Ο(1)

What about we don't want to have recursions? Then, we can use an extra linear space to store the FIB(n - 1) and FIB(n - 2) when computing FIB(n), which is to use *iteration* in replacement of *recursion* and having the same time complexity but avoid the use of recursion, which is also called **bottom-up DP**.

```


FIBONACCI(n)
  fib := {}
  for k in 1...n
    if k ⩽ 2
      f = 1
    else
      f = fib[n - 1] + fib[n - 2]
    fib[k] = f
  return fib[n]

```