递归方法

递归是方法调用自身的编程技巧。

递归概念

什么是递归

方法直接或间接调用自身，通过不断缩小问题规模解决问题。

// 递归特点
// 1. 方法调用自身
// 2. 有终止条件（避免无限递归）
// 3. 问题规模逐步缩小
// 4. 最终达到终止条件

递归结构

递归基本模式

public void recursive(参数) {
    if (终止条件) {
        return;  // 或返回结果
    }
    
    // 递归调用（问题规模缩小）
    recursive(新参数);
}

递归组成要素

• 终止条件：递归结束的条件
• 递归调用：方法调用自身
• 问题缩小：每次递归问题规模变小

public int factorial(int n) {
    // 终止条件
    if (n <= 1) {
        return 1;
    }
    
    // 递归调用（问题缩小）
    return n * factorial(n - 1);
}

递归示例

阶乘计算

// n! = n * (n-1) * ... * 1
public int factorial(int n) {
    if (n <= 1) {  // 终止条件
        return 1;
    }
    return n * factorial(n - 1);  // 递归调用
}

// 执行过程
factorial(5)
= 5 * factorial(4)
= 5 * 4 * factorial(3)
= 5 * 4 * 3 * factorial(2)
= 5 * 4 * 3 * 2 * factorial(1)
= 5 * 4 * 3 * 2 * 1
= 120

斐波那契数列

// fib(n) = fib(n-1) + fib(n-2)
// 1, 1, 2, 3, 5, 8, 13, 21...

public int fibonacci(int n) {
    if (n <= 2) {  // 终止条件
        return 1;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);  // 递归
}

// 计算第6个
fibonacci(6)  // 8

求和递归

// 计算1到n的和
public int sum(int n) {
    if (n <= 0) {
        return 0;
    }
    return n + sum(n - 1);
}

sum(5)  // 15 (5+4+3+2+1)

数组求和

public int arraySum(int[] arr, int index) {
    if (index >= arr.length) {
        return 0;
    }
    return arr[index] + arraySum(arr, index + 1);
}

int[] arr = {1, 2, 3, 4, 5};
arraySum(arr, 0);  // 15

数字各位之和

// 如 123 → 1+2+3 = 6
public int digitSum(int n) {
    if (n < 10) {
        return n;
    }
    return n % 10 + digitSum(n / 10);
}

digitSum(123);  // 6 (3 + 2 + 1)

递归执行过程

调用栈示意

factorial(5)调用栈：

factorial(5) 等待 factorial(4) 返回
factorial(4) 等待 factorial(3) 返回
factorial(3) 等待 factorial(2) 返回
factorial(2) 等待 factorial(1) 返回
factorial(1) 返回 1

然后依次返回：
factorial(2) 返回 2*1=2
factorial(3) 返回 3*2=6
factorial(4) 返回 4*6=24
factorial(5) 返回 5*24=120

递归图解

factorial(5)
    ↓
5 * factorial(4)
        ↓
    4 * factorial(3)
            ↓
        3 * factorial(2)
                ↓
            2 * factorial(1)
                    ↓
                返回1

经典递归问题

汉诺塔

// 将n个盘子从A移到C，借助B
public void hanoi(int n, char from, char aux, char to) {
    if (n == 1) {
        System.out.println(from + " → " + to);
        return;
    }
    
    // 将n-1个盘子从from移到aux
    hanoi(n - 1, from, to, aux);
    
    // 将最大盘子从from移到to
    System.out.println(from + " → " + to);
    
    // 将n-1个盘子从aux移到to
    hanoi(n - 1, aux, from, to);
}

hanoi(3, 'A', 'B', 'C');
// 输出：
// A → C
// A → B
// C → B
// A → C
// B → A
// B → C
// A → C

最大公约数

// 辗转相除法
public int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

gcd(48, 18);  // 6

反转字符串

public String reverse(String str) {
    if (str.isEmpty() || str.length() == 1) {
        return str;
    }
    return reverse(str.substring(1)) + str.charAt(0);
}

reverse("hello");  // "olleh"

递归注意事项

必须有终止条件

// 错误：无终止条件，无限递归
public void badRecursive() {
    badRecursive();  // 无限调用，StackOverflowError
}

// 正确：有终止条件
public void goodRecursive(int n) {
    if (n <= 0) {
        return;  // 终止
    }
    goodRecursive(n - 1);
}

避免栈溢出

递归过深会导致StackOverflowError。

// 深度递归可能栈溢出
public int deepRecursive(int n) {
    if (n == 0) return 0;
    return deepRecursive(n - 1) + 1;
}

// deepRecursive(100000);  // StackOverflowError

// 解决：使用迭代
public int iterative(int n) {
    int sum = 0;
    for (int i = 0; i <= n; i++) {
        sum += i;
    }
    return sum;
}

递归效率问题

某些递归效率低下，如斐波那契重复计算。

// 斐波那契递归效率低
fibonacci(10)
= fibonacci(9) + fibonacci(8)
= [fibonacci(8) + fibonacci(7)] + [fibonacci(7) + fibonacci(6)]
// fibonacci(7)被重复计算多次

// 优化：使用缓存或迭代
public int fibOptimized(int n) {
    if (n <= 2) return 1;
    
    int a = 1, b = 1;
    for (int i = 3; i <= n; i++) {
        int temp = a + b;
        a = b;
        b = temp;
    }
    return b;
}

递归与迭代对比

递归vs迭代

// 递归实现
public int sumRecursive(int n) {
    if (n <= 0) return 0;
    return n + sumRecursive(n - 1);
}

// 迭代实现
public int sumIterative(int n) {
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        sum += i;
    }
    return sum;
}

何时使用递归

适合递归场景

• 问题可自然分解为子问题
• 子问题与原问题结构相同
• 递归深度可控
• 树形结构遍历

// 树遍历适合递归
public void traverse(TreeNode node) {
    if (node == null) return;
    
    traverse(node.left);   // 左子树
    System.out.println(node.value);  // 当前节点
    traverse(node.right);  // 右子树
}

不适合递归场景

• 递归深度可能很大
• 效率要求高的场景
• 问题不适合分解

// 简单求和用迭代更好
// 不推荐递归
public int sum(int n) {
    int total = 0;
    for (int i = 1; i <= n; i++) {
        total += i;
    }
    return total;
}

要点总结

• 递归是方法调用自身
• 必须有终止条件避免无限递归
• 每次递归问题规模必须缩小
• 递归执行遵循调用栈（先进后出）
• 阶乘：n! = n * factorial(n-1)
• 斐波那契：fib(n) = fib(n-1) + fib(n-2)
• 汉诺塔、最大公约数是经典递归问题
• 深度递归可能栈溢出
• 效率低时考虑迭代替代
• 树遍历等结构问题适合递归
• 递归简洁，迭代高效