A recursion tree is a visual representation of recursive function calls. Each node represents a call with specific parameters, and edges show parent-child call relationships. It helps identify overlapping subproblems — a key insight for dynamic programming optimization. For Fibonacci, the tree reveals that F(n-2) is recomputed multiple times across different branches.

Naive recursion has O(2ⁿ) time complexity because each call spawns two more, leading to exponential growth. For F(50), this means over 40 billion calls — impractical on any machine. The tree visualization makes this explosion visible: the number of nodes doubles roughly every two levels.

Memoization stores previously computed results in a cache (dictionary/hash map). When the same subproblem appears again, the cached value is returned instantly instead of recursing again. This reduces Fibonacci from O(2ⁿ) to O(n) — a dramatic improvement. For F(50), memoized recursion needs only ~99 calls versus billions.

For F(n), there are only n+1 unique subproblems (F(0) through F(n)), but naive recursion makes 2F(n+1)−1 total calls. The overlap is massive: F(n−2) appears in both the F(n−1) and F(n−2) subtrees. Use the slider above to see how quickly overlapping calls multiply as n grows!

Top-down DP (memoization) starts from the original problem and recurses down, caching results. Bottom-up DP (tabulation) builds solutions iteratively from base cases upward — for Fibonacci, computing F(0), F(1), then F(2), F(3)... up to F(n). Both achieve O(n) time, but bottom-up avoids recursion overhead and stack overflow risks for large n.

Yes! Using matrix exponentiation or Binet's formula, Fibonacci can be computed in O(log n). The key insight: {{1,1},{1,0}}ⁿ yields F(n+1) and F(n). Combined with fast exponentiation (binary exponentiation), this achieves logarithmic time — ideal for huge n values like F(10¹⁸) modulo some number.