递归函数的基本结构

学习目标

本节学习递归函数的基本写法。

学习完成后，你需要能够识别一个递归函数中的三个部分：递归出口、递归调用和结果组合。理解这三个部分后，递归代码就不再只是“函数调用自己”，而是一种可分析、可设计的结构。

递归函数的三个部分

一个典型递归函数通常包含三个部分：

递归出口：最小规模问题的直接答案。
递归调用：把当前问题交给更小的同类问题。
结果组合：利用小问题结果构造当前问题答案。

以计算阶乘为例：

factorial(1) = 1
factorial(n) = n * factorial(n - 1)

其中 factorial(1) 是递归出口，factorial(n - 1) 是递归调用，n * ... 是结果组合。

阶乘递归示例

下面用四种语言实现阶乘递归：

int factorial(int n) {
    if (n == 1) {
        return 1;
    }

    return n * factorial(n - 1);
}

int factorial(int n) {
    if (n == 1) {
        return 1;
    }

    return n * factorial(n - 1);
}

def factorial(n):
    if n == 1:
        return 1

    return n * factorial(n - 1)

int Factorial(int n)
{
    if (n == 1)
    {
        return 1;
    }

    return n * Factorial(n - 1);
}

这四段代码表达的是同一个递归关系：先求较小问题 factorial(n - 1)，再乘以当前的 n。

递归出口要写在前面

通常建议先写递归出口，再写递归调用。

原因很简单：递归出口是停止条件。如果递归调用先发生，而停止条件没有及时判断，函数可能会无限调用下去。

例如，计算阶乘时，如果没有处理 n == 1，函数会继续调用 factorial(0)、factorial(-1)，最终无法正常停止。

递归参数必须靠近出口

递归调用时，参数通常应该让问题规模变小，并且越来越接近递归出口。

在阶乘中：

n -> n - 1 -> n - 2 -> ... -> 1

每次递归都让 n 减少 1，最终会到达 1。

如果递归参数没有变小，或者变化方向错误，递归就可能无法结束。

计算数组元素之和

递归不仅能处理数学公式，也能处理序列问题。

下面的函数计算数组前 n 个元素的和：

int sumFirstN(const vector<int>& numbers, int n) {
    if (n == 0) {
        return 0;
    }

    return sumFirstN(numbers, n - 1) + numbers[n - 1];
}

int sumFirstN(int[] numbers, int n) {
    if (n == 0) {
        return 0;
    }

    return sumFirstN(numbers, n - 1) + numbers[n - 1];
}

def sum_first_n(numbers, n):
    if n == 0:
        return 0

    return sum_first_n(numbers, n - 1) + numbers[n - 1]

int SumFirstN(int[] numbers, int n)
{
    if (n == 0)
    {
        return 0;
    }

    return SumFirstN(numbers, n - 1) + numbers[n - 1];
}

这里的递归含义是：前 n 个元素的和，等于前 n - 1 个元素的和，再加上第 n 个元素。

如何设计一个递归函数

设计递归函数时，可以按下面顺序思考：

1. 当前问题是什么？
2. 更小的同类问题是什么？
3. 最小问题是什么？
4. 如何用小问题结果得到当前答案？
5. 参数是否会逐步靠近最小问题？

如果这几个问题都能回答清楚，递归函数通常就比较容易写出来。

本节小结

递归函数通常由递归出口、递归调用和结果组合组成。

递归出口让函数停止，递归调用让问题规模变小，结果组合把小问题答案变成当前问题答案。设计递归时，要特别关注参数是否逐步靠近出口，否则递归可能无法结束。