Course contentsShow
← Computer Science
Lesson 222 of 2,8725. Functions and ModularityFree lesson

Fibonacci Sequence with Recursion

Implement the Fibonacci sequence recursively and observe the tree of recursive calls generated.

Fibonacci Sequence with Recursion

What you'll learn: How to implement the Fibonacci sequence using recursion and visualize the branching structure of recursive calls it creates.

What is the Fibonacci Sequence?

The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones: 0, 1, 1, 2, 3, 5, 8, 13, 21...

Mathematically: fib(n) = fib(n-1) + fib(n-2), with base cases fib(0) = 0 and fib(1) = 1.

Recursive Implementation

This naturally maps to recursion:

def fibonacci(n):
    # Base cases
    if n == 0:
        return 0
    if n == 1:
        return 1
    
    # Recursive case
    return fibonacci(n - 1) + fibonacci(n - 2)

When you call fibonacci(5), it doesn't immediately compute the answer. Instead, it spawns two more calls: fibonacci(4) and fibonacci(3). Each of those spawns two more, creating a tree of calls.

The Recursive Call Tree

For fibonacci(4), the tree looks like:

                  fib(4)
                /        \
           fib(3)          fib(2)
          /      \        /      \
      fib(2)   fib(1)  fib(1)  fib(0)
     /     \
  fib(1) fib(0)

Notice how fib(2) is computed twice and fib(1) appears three times. This redundancy grows exponentially—fibonacci(50) would take billions of calls! This demonstrates that while recursion is elegant, it isn't always efficient without optimization.

Key Takeaway: The Fibonacci sequence illustrates how recursion creates branching call trees; each function call may spawn multiple recursive calls, leading to exponential growth in computation without memoization or other optimizations.