数据结构与算法 --- 递归（二）

引言

上文数据结构与算法 --- 递归（一） 讲述了什么是递归算法，如何编写递归算法及如何写好递归算法，本文着重讲述一下如何避免递归过深导致的堆栈溢出问题。

探究产生堆栈溢出的原因

函数调用采用函数调用栈来保存当前“快照”（局部变量，返回地址等）。函数调用栈是内存中开辟的一块存储空间，它被组织成“栈”这种数据结构，数据先进后出。

递归的过程包含大量的函数调用，如果递归求解的数据规模很大，函数调用层次很深，那么函数调用栈中的数据（栈帧）会越来越多，而函数调用栈空间一般不大，堆栈空间不足以存储所有的调用信息，从而导致堆栈溢出。

以计算阶乘举例，代码如下：

public int Factorial(uint n)
{
    if (n <= 1) return 1;

    return n * Factorial(n - 1);
}

当 Factorial(n) 执行到 Factorial(n - 1) 是，编译器将局部变量，n 和 Factorial(n - 1) 的返回地址封装为一个栈帧，保存在函数调用栈内，然后再跳转到 Factorial(n - 1) 函数体内。

在 Factorial(n - 1) 执行完成之后，返回结果（假设是 result ），编译器就从函数调用栈中取出之前保存的栈帧（局部变量 n 和Factorial(n - 1) 的返回地址）。通过返回地址，编译器就知道之前执行到了哪条语句（即 return n * Factorial(n - 1) 这条语句），就可以接着从这条语句继续往下执行：将栈帧中保存的 n 的值，与 Factorial(n - 1) 的结果（即 result ）相乘后将结果返回。

那如果不在函数调用栈中存储局部变量，返回地址等信息，是否可行呢？

答案肯定是不行。

• 若不存储返回地址，那么 Factorial(n - 1) 执行完之后，编译器就不知道该从哪里继续执行。
• 若不存储局部变量，那么 Factorial(n - 1) 执行完之后，编译器即使知道该从哪里执行，但不知道 n 的值，也就无法计算 n * Factorial(n - 1) 并返回了。

讨论尾递归避免堆栈溢出

什么是尾递归？

尾递归是指一个递归函数的最后一个操作是递归调用自身，并且该调用的返回值直接返回给函数的调用者，而不进行任何其他的计算或处理。这种形式的递归称为尾递归。

在尾递归中，递归调用是函数的最后一步操作，因此不需要再次回到递归调用之前的位置来执行其他操作。这意味着尾递归可以被优化为循环，从而避免了递归调用带来的栈空间开销和性能问题。

例如将上述阶乘代码转化为尾递归代码如下：

public int Factorial(uint n, int res)
{
    if (n <= 1) return res;
    return Factorial(n - 1, (int)(n * res));
}

从理论上来说，尾递归是又可能解决堆栈溢出的问题的。

上文说到，函数调用栈中保存局部变量和返回地址，而对于尾递归代码，递归代码出现在最后一行中，返回之后不需要继续往下执行，因此，返回地址可以不用保存；而局部变量 n 也被移动到新的函数 Factorial(n - 1, n * res) 中，也不需要保存到栈中。所以对于尾递归代码，不需要想栈里压入数据，也就不存在堆栈溢出的问题。

但是在实际开发过程中，尾递归其实并没有太大作用，不能期望它来规避递归导致的堆栈溢出问题，主要表现在：

• 并不是所有编程语言都支持尾递归优化
• 并不是所有的递归都可以改成尾递归
• 能改成尾递归的代码也就都可以改成迭代方式
• 尾递归代码的可读性差

参考资料

[1] 数据结构与算法之美 / 王争 著. --北京：人民邮电出版社，2021.6