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.