第6.11章: 递归函数

概述

递归函数是调用自身的函数。 递归是表达那些可以拆解为同形式更小子问题的自然方式。

在本章中，你将学到：

• 什么是递归
• 如何编写正确的递归函数
• 基准情形（base case）的重要性
• 递归如何使用调用栈
• 为什么尾递归在 C++ 中不保证被优化
• 何时适合用递归，何时用迭代更好

1. 什么是递归？

递归函数通过解决同一问题的更小版本来解决该问题。每个递归函数都必须有：

• 基准情形 —— 何时停止
• 递归情形 —— 如何缩小问题

没有基准情形，递归永远不会结束，程序最终会因栈耗尽而崩溃。

2. 示例：阶乘

阶乘函数在数学上定义为：

n! = n × (n - 1)!  
0! = 1
      

这个定义天生就是递归的。

int factorial(int n)
{
    if(n < 0)
        ::fast_io::fast_terminate(); // factorial is undefined for negatives

    if(n == 0)
        return 1;                    // base case

    return n * factorial(n - 1);     // recursive case
}

每次调用都会缩小问题，直到抵达基准情形。

3. 递归如何使用调用栈

每次函数调用都会创建一个新的栈帧，其中包含：

• 形参
• 局部变量
• 返回地址

递归函数每次递归调用都会创建一个栈帧。例如：

factorial(4)
 ├─ factorial(3)
 │   ├─ factorial(2)
 │   │   ├─ factorial(1)
 │   │   │   └─ factorial(0)

当基准情形返回时，栈按相反顺序展开。

如果递归太深，程序会因栈溢出而崩溃。

4. 尾递归

尾递归函数是指递归调用是函数中最后一步操作的函数。

int sum_tail(int n, int acc)
{
    if(n == 0)
        return acc;          // base case

    return sum_tail(n - 1, acc + n); // tail call
}

在某些语言中，尾递归会被优化成循环。然而：

C++ 并不保证尾调用优化。

编译器可能优化尾递归，但你不能依赖它。如果你需要保证栈用量的常量性， 请改写成显式循环。

5. 何时适合使用递归

递归在以下情况很合适：

• 问题本身就是递归的（树、图、分治）
• 递归结构与数学定义相符
• 深度很小且可预测

递归在以下情况不合适：

• 深度可能很大或没有上界
• 栈用量是关注点
• 迭代更简单、更清晰

6. 更多示例

6.1 斐波那契（低效的递归版本）

int fib(int n)
{
    if(n < 0)
        ::fast_io::fast_terminate();

    if(n <= 1)
        return n;

    return fib(n - 1) + fib(n - 2);
}

这个版本极其缓慢，因为它会反复重算相同的值。 迭代版或记忆化版本更好。

要点

• 递归函数调用自身来解决更小的子问题。
• 每个递归函数都需要基准情形与递归情形。
• 递归使用调用栈；深递归有栈溢出的风险。
• C++ 不保证尾调用优化。
• 当递归与问题结构相符时使用它；当迭代更简单或更安全时使用迭代。