Back to Recursion

Fibonacci Sequence Recursion

See the explosive growth of naive recursion vs the efficiency of memoization in computing Fibonacci numbers.

Exponential vs Linear
O(2^n) vs O(n)
Memoization Magic

Controls

fib(5) = 5
Algorithm Mode:
🔥 Recalculating everything from scratch

Performance Stats

Current calls:0
Naive total:15
Memoized total:6
Speedup: 3x faster with memoization!

Current Step

Step 1 of 0

Click Start to begin the Fibonacci visualization

Current Call:

Call Tree VisualizationNAIVE

Click Start to see the call tree in action

Python Implementation

def fibonacci_naive(n):
    # Base case
    if n <= 1:
        return n
    
    # Recursive case - exponential time!
    return fibonacci_naive(n-1) + fibonacci_naive(n-2)

def fibonacci_memo(n, memo={}):
    # Check cache first
    if n in memo:
        return memo[n]
    
    # Base case
    if n <= 1:
        memo[n] = n
        return n
    
    # Compute and cache result
    memo[n] = fibonacci_memo(n-1, memo) + fibonacci_memo(n-2, memo)
    return memo[n]

# Example: fib(5) = 5
# Naive calls: 15 vs Memoized calls: 6

JavaScript Implementation

function fibonacciNaive(n) {
    if (n <= 1) return n;
    return fibonacciNaive(n-1) + fibonacciNaive(n-2);
}

function fibonacciMemo(n, memo = {}) {
    if (n in memo) return memo[n];
    if (n <= 1) {
        memo[n] = n;
        return n;
    }
    memo[n] = fibonacciMemo(n-1, memo) + fibonacciMemo(n-2, memo);
    return memo[n];
}

// Example: fib(5) = 5

Algorithm Analysis

Naive Recursion

  • • Time: O(2^n) - exponential growth
  • • Space: O(n) - recursion depth
  • • Calls: 15 for fib(5)
  • • Recalculates same values repeatedly
  • • Becomes unusably slow for n > 35

With Memoization

  • • Time: O(n) - linear time
  • • Space: O(n) - cache + recursion
  • • Calls: 6 for fib(5)
  • • Each value computed only once
  • • Dramatically faster for large n

Real-World Applications

  • • Nature: Flower petals, spiral shells, bee genealogy
  • • Finance: Elliott wave theory, market analysis
  • • Computer Science: Algorithm analysis, golden ratio
  • • Art/Design: Golden rectangle, architectural proportions
  • • Biology: DNA structure, population growth models
  • • Optimization: Dynamic programming introduction