Three implementations with a timing comparison demonstrating the practical impact of algorithm choice. See Fibonacci sequence — Wikipedia.
| Function | Approach | Time complexity | Space complexity |
|---|---|---|---|
fib(n) |
Naive recursion | O(2ⁿ) | O(n) call stack |
fib_iterative(n) |
Iterative | O(n) | O(1) |
fib_memo(n) |
Memoized recursion | O(n) | O(n) |
Memoization stores the result of each function call so it is never computed twice. The memoized version has the simplicity of recursion but the efficiency of iteration.
python fibonacci.pyPrints the first 10 values then a timing table for n = 1 to 35.