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 nth member of the Fibonacci sequence, based directly on the mathematical definition:
function fib(n) if n <= 1 return n return fib(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(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))
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):
var m := map(0 → 0, 1 → 1) function fib(n) if key n is not in map m m[n] := fib(n − 1) + fib(n − 2) return m[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.
function fib(n) if n = 0 return 0 else var previousFib := 0, currentFib := 1 repeat n − 1 times // loop is skipped if n = 1 var newFib := previousFib + currentFi