### Fibonacci sequence[edit]

This section
does not cite any sources. (May 2013) (Learn how and when to remove this template message) |

Here is a naïve implementation of a function finding the *n*th member of the Fibonacci sequence, based directly on the mathematical definition:

functionfib(n)ifn <= 1returnnreturnfib(n − 1) + fib(n − 2)

Notice that if we call, say, `fib(5)`

, we produce a call tree that calls the function on the same value many different times:

`fib(5)`

`fib(4) + fib(3)`

`(fib(3) + fib(2)) + (fib(2) + fib(1))`

`((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))`

`(((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))`

In particular, `fib(2)`

was calculated three times from scratch. In larger examples, many more values of `fib`

, or *subproblems*, are recalculated, leading to an exponential time algorithm.

Now, suppose we have a simple map object, *m*, which maps each value of `fib`

that has already been calculated to its result, and we modify our function to use it and update it. The resulting function requires only O(*n*) time instead of exponential time (but requires O(*n*) space):

varm :=(0 → 0, 1 → 1)mapfunctionfib(n)ifnkeyis not inm m[n] := fib(n − 1) + fib(n − 2)mapreturnm[n]

This technique of saving values that have already been calculated is called *memoization*; this is the top-down approach, since we first break the problem into subproblems and then calculate and store values.

In the **bottom-up** approach, we calculate the smaller values of `fib`

first, then build larger values from them. This method also uses O(*n*) time since it contains a loop that repeats n − 1 times, but it only takes constant (O(1)) space, in contrast to the top-down approach which requires O(*n*) space to store the map.

functionfib(n)ifn = 0return0elsevarpreviousFib := 0, currentFib := 1repeatn − 1times// loop is skipped if n = 1varnewFib := previousFib + currentFi