递归常见问题与调试方法

学习目标

本节总结递归中常见的问题和调试方法。

递归难点不只在写代码，更在于理解执行过程。初学者常见错误包括缺少递归出口、参数没有靠近出口、边界条件写错、重复计算过多，以及无法判断每一层到底返回了什么。

---

问题一：没有递归出口

没有递归出口会导致无限递归。

C++

int bad(int n) {
    return bad(n - 1);
}

Java

int bad(int n) {
    return bad(n - 1);
}

Python

def bad(n):
    return bad(n - 1)

C#

int Bad(int n)
{
    return Bad(n - 1);
}

这段代码没有任何停止条件，因此会一直调用下去。写递归函数时，第一步就应该明确递归出口。

---

问题二：参数没有靠近出口

有些递归虽然写了出口，但参数变化方向不对，也会导致无法停止。

例如，出口是 n == 0，但递归调用却让 n 越来越大：

C++

int bad(int n) {
    if (n == 0) {
        return 0;
    }

    return bad(n + 1);
}

Java

int bad(int n) {
    if (n == 0) {
        return 0;
    }

    return bad(n + 1);
}

Python

def bad(n):
    if n == 0:
        return 0

    return bad(n + 1)

C#

int Bad(int n)
{
    if (n == 0)
    {
        return 0;
    }

    return Bad(n + 1);
}

如果一开始 n 是正数，它会越来越远离 0。

---

问题三：边界条件写错

递归最容易出错的地方是边界。

例如处理数组时，要特别注意空数组、单个元素、下标是否越界等情况。

一个常见原则是：先把最小规模问题写清楚。对于数组问题，最小规模常常是长度为 0 或 1；对于树问题，最小规模常常是空节点；对于字符串问题，最小规模常常是空字符串或单个字符。

---

问题四：重复计算过多

有些递归会重复计算大量相同子问题。

典型例子是斐波那契数列的朴素递归：

C++

int fib(int n) {
    if (n <= 1) {
        return n;
    }

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

Java

int fib(int n) {
    if (n <= 1) {
        return n;
    }

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

Python

def fib(n):
    if n <= 1:
        return n

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

C#

int Fib(int n)
{
    if (n <= 1)
    {
        return n;
    }

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

这个函数非常符合递归定义，但会重复计算很多次。例如 fib(5) 会多次计算 fib(3) 和 fib(2)。

这类问题后续可以通过记忆化搜索或动态规划优化。

---

递归调试方法

调试递归时，可以按下面步骤进行：

1. 写出最小输入，确认递归出口是否正确。

2. 手动展开一两个小规模例子，例如 n = 3 或数组长度为 3。

3. 在递归调用前后打印参数和返回值。

4. 检查每次递归参数是否更接近出口。

5. 检查当前层是否正确使用了子问题返回结果。

6. 如果递归太深，考虑是否可以改成迭代或增加剪枝、记忆化。

调试递归不要一开始就用很大的输入。先用小规模例子观察执行过程，往往更容易发现问题。

---

写递归前的检查清单

写递归函数前，可以先回答下面几个问题：

1. 当前函数的含义是什么？
2. 输入参数分别代表什么？
3. 最小问题是什么？
4. 递归出口是什么？
5. 如何把当前问题拆成更小问题？
6. 更小问题的答案如何组成当前答案？
7. 参数是否一定会越来越接近出口？

如果这些问题说不清楚，直接写代码通常会很容易出错。

---

本节小结

递归常见问题包括没有出口、参数不靠近出口、边界条件错误和重复计算过多。

调试递归时，不要只盯着最终结果。要关注每一层函数的含义、参数变化、返回值和调用深度。只要能把递归出口和递归关系讲清楚，递归代码就会变得更可控。