请注意,本文编写于 303 天前,最后修改于 295 天前,其中某些信息可能已经过时。

目录

引言
探究产生堆栈溢出的原因
讨论尾递归避免堆栈溢出

引言

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

探究产生堆栈溢出的原因

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

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

以计算阶乘举例,代码如下:

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

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

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

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

答案肯定是不行。

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

讨论尾递归避免堆栈溢出

什么是尾递归?

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

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

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

csharp
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

本文作者:Peter.Pan

本文链接:

版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!