C语言论递归函数及其本质

一个函数在函数体内又调用了本身，我们称为递归调用，这样的函数就是递归函数。

递归函数成功执行需满足以下两个条件：

1. 必须有一个明显的结束条件。
2. 必须有一个趋近于结束条件的趋势。

举个生活例子：数钱

假设你有一叠钞票，想知道总数，但只能一张一张数。递归的做法是：

1. 终止条件：如果只剩一张钞票，直接返回 1。

2. 递归步骤：每次数一张，然后把剩下的钞票交给“另一个人”用同样的方法数（实际上还是你自己数，但问题规模变小了）。

用代码表示：

int count_money(int n) {
    if (n == 1) {        // 终止条件：只剩一张
        return 1;
    } else {             // 递归步骤：数一张，剩下的交给下一层
        return 1 + count_money(n - 1);
    }
}

当你调用 count_money(5)，实际执行过程是：
5 → 4 → 3 → 2 → 1（终止条件满足），然后倒着返回结果：
1 → 2 → 3 → 4 → 5，最终得到总数 5。

递归的底层原理

计算机通过栈（Stack） 来管理递归调用：

• 每次调用函数时，当前状态（变量值、执行位置等）会被压入栈中。

• 遇到终止条件后，开始从栈顶一层层弹出状态，倒着计算结果。

• 如果递归太深（比如没有终止条件），栈会被塞满，导致程序崩溃（Stack Overflow）。

“倒着返回结构”的本质是栈的 FILO 特性，它强制递归函数先解决最小的问题，再逐层回溯解决更大的问题。这种机制虽然直观，但需要警惕栈溢出的风险（例如无终止条件的递归）。理解递归的关键是想象调用栈如何逐步展开和回溯。

递归 vs 循环

• 递归：像俄罗斯套娃，一层层打开直到最小的娃娃，再一层层装回去。代码简洁，但可能效率低（占用内存多）。

• 循环：像流水线作业，从头到尾直接处理。效率高，但代码可能更复杂。

什么时候用递归？

适合处理自相似问题（大问题能分解成小问题，且小问题和大问题的解法相同）：

• 阶乘计算（5! = 5 × 4!）

• 斐波那契数列（fib(n) = fib(n-1) + fib(n-2)）

• 遍历树或文件夹结构（一个文件夹里可能有子文件夹）

总结：递归就是“把大象装进冰箱，但冰箱里还有一个冰箱，直到遇到一个空冰箱”——关键在于找到终止条件，否则永远装不完！ 🐘❄️