Imagine you’re telling a friend a story about “finding something.” Your friend asks, “Which shelf is this book on?” You can’t remember the exact position, only that it’s in the middle of the bookshelf—but there are many middle shelves. You might say, “I’ll ask the person on the top shelf if they know the lower positions?” No, maybe a simpler example: Recursion is like when you solve a problem and realize, “This problem requires solving two smaller problems first,” and these two smaller problems are of the same type as the original problem.
一、What is Recursion?¶
The literal meaning of recursion is “calling oneself,” but more accurately, it’s a method where you break a large problem into smaller problems of the same type. You continue this until the problem is small enough to solve directly (called the “base case”), then use the results of the small problems to infer the result of the large problem.
A relatable example:
You want to know the height of the 10th student in your class (assuming you know everyone’s height), but you can’t remember who they are. So you ask, “What are the heights of the 9th and 8th students?”
The 9th student asks the 8th and 7th, the 8th asks the 7th and 6th… until you reach the 1st student (where the answer is known). Then you return the results layer by layer to finally calculate the 10th student’s height.
二、Fibonacci Sequence: A Classic Recursion Application¶
The Fibonacci sequence is a classic recursion case with a simple definition:
- The 0th number (F(0)) is 0
- The 1st number (F(1)) is 1
- Starting from the 2nd number, each number equals the sum of the two preceding ones: F(n) = F(n-1) + F(n-2) (for n > 1)
For example:
F(0) = 0, F(1) = 1, F(2) = F(1)+F(0) = 1, F(3) = F(2)+F(1) = 2, F(4) = F(3)+F(2) = 3, F(5) = F(4)+F(3) = 5…
三、Calculating Fibonacci with Recursion¶
Let’s use recursion to compute F(5) and see how it “breaks down” the problem:
1. Base Case: The Smallest Problem¶
When n=0, return 0 directly; when n=1, return 1 directly. These are known base cases that don’t need further decomposition.
2. Recursive Case: Breaking Down the Large Problem¶
To compute F(n), you must first compute F(n-1) and F(n-2), then sum the results.
Step-by-Step Calculation of F(5) (Bottom-Up):¶
- F(5) = F(4) + F(3)
- F(4) = F(3) + F(2)
- F(3) = F(2) + F(1)
- F(2) = F(1) + F(0) = 1 + 0 = 1 (base case)
- F(3) = F(2) + F(1) = 1 + 1 = 2 (result obtained)
- F(4) = F(3) + F(2) = 2 + 1 = 3 (result obtained)
- F(5) = F(4) + F(3) = 3 + 2 = 5 (final result)
四、The Core of Recursion: Decomposition and Termination¶
Recursion isn’t “confusing” because it follows two rules:
1. Base Case: There must be a clear “no need to decompose further” scenario (e.g., F(0) and F(1)), otherwise, it will loop infinitely.
2. Decreasing Problem Size: Each recursive call reduces the problem size (e.g., n decreases from 5 to 4 and 3, then to smaller numbers), ensuring you eventually reach the base case.
五、Recursive Code Implementation (Python Example)¶
You can write a recursive Fibonacci function in just a few lines:
def fibonacci(n):
if n == 0: # Base case 1: return 0 when n=0
return 0
elif n == 1: # Base case 2: return 1 when n=1
return 1
else: # Recursive case: decompose into two smaller problems
return fibonacci(n-1) + fibonacci(n-2)
# Test: Calculate F(5)
print(fibonacci(5)) # Output: 5
六、Recursion Summary¶
Recursion is like “task decomposition”:
- First, split the big problem into two “small problems” until they’re small enough to solve directly.
- After solving the small problems, combine their results to get the answer for the big problem.
The recursive implementation of the Fibonacci sequence solves the calculation of “large-number Fibonacci values” with the simplest logic (decomposition + base case). While recursion might seem “complex,” it makes the code more concise and embodies the wisdom of “retreating to advance”—solve small problems first, then tackle the big ones.
Thought: What if you used iteration (looping) instead of recursion to calculate Fibonacci numbers? Try comparing the two methods, e.g., calculating F(100) will be much slower with recursion (why?), but recursion has shorter code. This is the “elegance” and “cost” of recursion.