I. What is Recursion?¶

Recursion, simply put, means “calling itself”. Imagine a Russian nesting doll: you have a large doll containing a smaller one, which in turn contains an even smaller one, and so on, until the smallest doll holds no more dolls. Recursion works similarly— a problem is broken down into smaller subproblems, each of which is a scaled-down version of the original problem. Once the subproblems are small enough to solve directly (no further decomposition needed), the results “bounce back” to form the final answer.

II. Core of Recursion: Termination Condition + Recursive Relation¶

Recursion has two essential elements, both of which are required:
1. Termination Condition: When the problem is small enough to be solved directly, return the result immediately (to avoid infinite loops).
2. Recursive Relation: How to break the large problem into smaller subproblems, where each subproblem is solved using the same rule.

III. Learning Recursion with the Fibonacci Sequence¶

The Fibonacci sequence is a classic example of recursion, defined as follows:
- The 0th term is 0 (F(0) = 0)
- The 1st term is 1 (F(1) = 1)
- For terms beyond the 1st, each term equals the sum of the two preceding terms (F(n) = F(n-1) + F(n-2))

Let’s use recursion to find the nth Fibonacci number:

1. Define the Recursive Function¶

Suppose we write a function fib(n) to return the nth Fibonacci number:

def fib(n):
    # Termination condition: return directly if n is 0 or 1
    if n == 0:
        return 0
    if n == 1:
        return 1
    # Recursive relation: break into smaller subproblems (call itself)
    return fib(n-1) + fib(n-2)

2. Dissect the Recursive Process with an Example¶

Let’s take fib(5) to see how recursion computes step by step:
- To compute fib(5), we first need fib(4) and fib(3);
- To compute fib(4), we need fib(3) and fib(2);
- To compute fib(3), we need fib(2) and fib(1);
- To compute fib(2), we need fib(1) and fib(0);
- When we reach fib(1) or fib(0), we return the value directly (1 or 0, respectively).

Returning Results Layer by Layer:
- fib(2) = fib(1) + fib(0) = 1 + 0 = 1
- fib(3) = fib(2) + fib(1) = 1 + 1 = 2
- fib(4) = fib(3) + fib(2) = 2 + 1 = 3
- fib(5) = fib(4) + fib(3) = 3 + 2 = 5

Thus, the 5th Fibonacci number is 5.

IV. The “Routine” of Recursion: Nesting and Bottom-Up Return¶

The recursion process is like “peeling an onion”: start from the outermost problem, dig layer by layer inward until reaching the innermost simple problem (the termination condition), then return results layer by layer. A recursion without a termination condition will cause infinite loops—for example, forgetting to handle n==0 or n==1 will make the program call itself indefinitely until it crashes.

V. Pros and Cons of Recursion (Brief)¶

• Pros: Clear logic, easy to understand and implement (e.g., the Fibonacci sequence can be solved with just a few lines of recursion).
• Cons: May lead to redundant calculations (e.g., fib(3) is computed twice in fib(5)), resulting in lower efficiency. For optimization, use “memoized recursion” or “iteration” instead.

VI. Summary¶

The essence of recursion is “breaking a large problem into smaller ones, solving the smaller ones, and then combining their results to get the final answer”. Using the Fibonacci sequence, we saw how recursion implements self-invocation through “termination condition + recursive relation” to obtain the answer. Remember: the key is to ensure recursion does not “go too far”—it must be able to “return”!

Next time you encounter a problem that can be decomposed into identical subproblems, try recursion. It might just simplify the solution dramatically!