递归

递归（recursion）是方法调用自己的过程。递归可以把复杂问题拆成更小的同类问题，但它也更容易造成重复计算和调用栈增长。

递归的两个条件

一个递归方法（recursive method）通常需要两部分：

• 基本情况（base case）：不再继续递归，直接返回结果。
• 递归情况（recursive case）：把问题缩小，然后调用自己。

如果没有基本情况，方法会一直调用自己，最终导致栈溢出（stack overflow）。

static void tell_story() {
    System.out.println("从前有座山，山里有座庙");
    System.out.println("庙里有个老和尚");
    System.out.println("老和尚在对小和尚讲故事：");
    tell_story();
}

每次调用 tell_story()，都会先输出三句话，然后再次调用自己，就像故事里又开始讲同一个故事。这个反例没有停止条件，因此不能正常结束；实际运行会不断增加调用栈，最终触发 StackOverflowError。这里只用它观察“方法调用自己”的结构，不要把它当作可以正常完成的程序。

阶乘

阶乘（factorial）是递归入门的经典例子。

static long factorial(int n) {
    if (n == 0) {
        return 1;
    }
    return n * factorial(n - 1);
}

运行结果：

5! = 120

factorial(5) 不会马上得到结果。它会先调用 factorial(4)，再调用 factorial(3)，直到遇到 factorial(1)。然后结果才会一层层返回。

Ackermann 方法

Ackermann 方法是一个经典递归例子。它不像阶乘那样只把 n 减 1，而是根据 m 和 n 的组合进入不同递归分支。

static long ackermann(long m, long n) {
    if (m == 0) {
        return n + 1;
    }
    if (n == 0) {
        return ackermann(m - 1, 1);
    }
    return ackermann(m - 1, ackermann(m, n - 1));
}

运行结果：

7

这个方法非常适合观察“递归里面再嵌套递归”的结构，但它增长极快。初学时只用很小的输入，例如 ackermann(2, 2) 或 ackermann(3, 1)。

下表展示 m = 0…3、n = 0…4 时的结果。前三行增长较平缓，但到了 m = 3，向右移动一步时，结果几乎会在前一个值的基础上翻倍后继续增加：

表格在 m = 4 前停止，因为它会从 A(4,0) = 13 跳到 A(4,1) = 65533，再往后的结果已经不适合直接计算和展示。

递归的代价

递归代码常常很简洁，但每一次递归都会产生一次方法调用。如果问题规模很大，递归可能会非常慢，甚至导致栈溢出。

以斐波那契数列（Fibonacci sequence）为例：

static long fibonacci(int n) {
    if (n == 1 || n == 2) {
        return 1;
    }
    return fibonacci(n - 2) + fibonacci(n - 1);
}

运行结果：

13

这个递归版本会重复计算很多次。例如 fibonacci(5) 和 fibonacci(4) 内部都会继续计算 fibonacci(3)。对于较大的 n，这种重复会变得非常明显。

汉诺塔

有些问题天生适合递归。汉诺塔（Tower of Hanoi）的思路是：

1. 把上面的 n - 1 个盘子从源柱移动到辅助柱。
2. 把最大盘从源柱移动到目标柱。
3. 把 n - 1 个盘子从辅助柱移动到目标柱。

static void hanoi(int n, char from, char helper, char to) {
    if (n == 0) {
        return;
    }
    hanoi(n - 1, from, to, helper);
    System.out.println(from + " -> " + to);
    hanoi(n - 1, helper, from, to);
}

运行结果：

A -> C
A -> B
C -> B
A -> C
B -> A
B -> C
A -> C
移动次数：7

每一步看起来只是移动一个盘子，但背后的递归任务是“先移动上面的 n - 1 个盘子，再移动最大的盘子”。下面的组件可以逐步观察盘子如何在三根柱子之间移动。

递归不是为了“看起来高级”，而是为了让某些本来就具有自相似结构的问题更容易表达。