What is Recursion?¶

In programming, recursion is a process where a method calls itself directly or indirectly. To understand recursion, two key points are crucial: termination condition (when to stop recursing) and recursive relation (how to decompose the problem).

Imagine a real-life example: you want to know how many candies are in a nested box. You can only start from the outermost box, open one box at a time to check the candies inside, until you reach the innermost box. Here, “opening a box” is the recursive operation, and “the box is empty” is the termination condition.

Core Principles of Recursion¶

The execution of recursion can be analogized to “peeling an onion”: each recursive call solves a “smaller subproblem” until reaching the smallest problem that cannot be decomposed further (the termination condition). Then, results are returned layer by layer.

From a computer execution perspective, each recursive call creates a new frame on the memory’s “method call stack” to store the current method’s parameters, local variables, and return address. When the termination condition is met, the innermost method returns first, and outer methods then compute and return results sequentially.

Example 1: Factorial¶

Factorial is a classic recursive example. Its mathematical definition is:
- \( n! = n \times (n-1) \times (n-2) \times \dots \times 1 \)
- Special cases: \( 0! = 1 \), \( 1! = 1 \)

Recursive Implementation Idea:
1. Termination Condition: When \( n = 0 \) or \( n = 1 \), return 1.
2. Recursive Relation: When \( n > 1 \), return \( n \times \text{factorial}(n-1) \).

Java Code Implementation:

public class RecursionExample {
    // Recursive factorial method
    public static long factorial(int n) {
        // Termination condition: negative n is invalid
        if (n < 0) {
            throw new IllegalArgumentException("Factorial parameters cannot be negative");
        }
        // Termination condition: n=0 or n=1 returns 1
        if (n == 0 || n == 1) {
            return 1;
        }
        // Recursive relation: n * (n-1)!
        return n * factorial(n - 1);
    }

    public static void main(String[] args) {
        int num = 5;
        long result = factorial(num);
        System.out.println(num + "! = " + result); // Output: 5! = 120
    }
}

Execution Process Analysis:
- Call factorial(5) → Need to compute \( 5 \times \text{factorial}(4) \)
- factorial(4) → \( 4 \times \text{factorial}(3) \)
- factorial(3) → \( 3 \times \text{factorial}(2) \)
- factorial(2) → \( 2 \times \text{factorial}(1) \)
- factorial(1) → Meets termination condition, returns 1
- Return layer by layer: \( 2 \times 1 = 2 \) → \( 3 \times 2 = 6 \) → \( 4 \times 6 = 24 \) → \( 5 \times 24 = 120 \)

Example 2: Fibonacci Sequence¶

The Fibonacci sequence is defined as:
- \( F(0) = 0 \), \( F(1) = 1 \)
- For \( n > 1 \), \( F(n) = F(n-1) + F(n-2) \)

Recursive Implementation Idea:
1. Termination Condition: Return 0 when \( n = 0 \), return 1 when \( n = 1 \).
2. Recursive Relation: For \( n > 1 \), return \( F(n-1) + F(n-2) \).

Java Code Implementation:

public class RecursionExample {
    // Recursive Fibonacci method
    public static long fibonacci(int n) {
        // Termination condition: negative n is invalid
        if (n < 0) {
            throw new IllegalArgumentException("Fibonacci parameters cannot be negative");
        }
        // Termination conditions
        if (n == 0) {
            return 0;
        } else if (n == 1) {
            return 1;
        }
        // Recursive relation: F(n) = F(n-1) + F(n-2)
        return fibonacci(n - 1) + fibonacci(n - 2);
    }

    public static void main(String[] args) {
        int n = 5;
        long result = fibonacci(n);
        System.out.println("Fibonacci(" + n + ") = " + result); // Output: Fibonacci(5) = 5
    }
}

Execution Process Analysis:
- Calculating \( F(5) \) requires recursive calls \( F(4) + F(3) \)
- \( F(4) = F(3) + F(2) \), \( F(3) = F(2) + F(1) \), and so on until \( F(1) = 1 \) and \( F(0) = 0 \)
- Final result: \( F(5) = 5 \)

Advantages, Disadvantages, and Precautions of Recursion¶

Advantages:¶

• Clear Logic: Suitable for describing mathematical problems with recursive relationships (e.g., factorial, Fibonacci, Tower of Hanoi).
• Concise Code: Directly translate mathematical definitions into code without complex loops.

Disadvantages:¶

• Stack Overflow Risk: Excessive recursion depth (e.g., calculating \( 1000! \)) causes StackOverflowError (exhausted call stack).
• Efficiency Issues: Some recursions have redundant calculations (e.g., Fibonacci recursion repeatedly computes \( F(3) \)), which can be optimized with memoization.

Precautions:¶

1. Must Have Termination Condition: Otherwise, infinite recursion occurs (e.g., forgetting the n == 0 condition in factorial leads to infinite calls to factorial(-1) until crash).
2. Parameter Range: Recursive parameters must decrease gradually to avoid infinite loops (e.g., passing n+1 instead of n-1 increases parameters).
3. Data Type: Factorial results grow rapidly, so use long instead of int (e.g., \( 13! = 6227020800 \) exceeds int range).

Summary¶

Recursion is a powerful tool for solving “self-similar problems”. Its core is decomposing the problem into smaller subproblems and terminating at the smallest subproblem. Beginners should start with simple scenarios (e.g., factorial), understand the call stack and termination conditions, then gradually apply it to complex scenarios (e.g., Fibonacci, tree traversal). In practice, if recursion depth is too large or redundancy is severe, use loops or dynamic programming instead, but the recursive thinking remains valuable to master.