尾递归 作者：马育民 • 2024-12-31 23:04 • 阅读：10004 # 普通递归的缺点 以阶乘为例，下面代码是普通递归： ``` def fib(n): if n == 0: return 1 return fib(n - 1) * n ``` 调用函数： ``` fib(4) ``` 递归调用过程，会变成如下的形式： ``` fib(3) * 4 fib(2) * 3 * 4 fib(1) * 2 * 3 * 4 fib(0) * 1 * 2 * 3 * 4 1 * 1 * 2 * 3 * 4 1 * 2 * 3 * 4 2 * 3 * 4 6 * 4 24 ``` ### 缺点 可以看出，在每次递归调用的时候，系统都会开辟 **一个内存空间，保存临时变量**，当n过于大时，需要开辟的内存空间就过大，就可能导致 **栈内存溢出**。 # 尾递归 把上面的函数写成如下形式： ``` def fib(n, acc=1): if n == 0: return acc return fibl(n - 1, n * acc) ``` 调用函数： ``` fib(4, 1) ``` 递归调用过程，会变成如下的形式： ``` fib(3, 4) fib(2, 12) fib(1, 24) fib(0, 24) 24 ``` ### 优点 很直观的就可以看出，这次的 `fib` 函数在递归调用的时候 **不会 开辟多余内存空间**，产生一系列逐渐增多的中间变量了，而是 **将状态保存在 `acc` 这个变量中** 而这种形式的递归，就叫做尾递归 ### 概念 尾递归的定义顾名思义，函数调用中，最后返回的结果，**是单纯的递归函数调用（或返回结果）**，就是尾递归。 ### 特点 总的来说，尾递归在递归过程中最后一步执行递归函数的步骤，并且在函数结束前不再需要执行任何其他计算或操作 而常规递归则在递归嵌套过程中创建多个栈帧以保存函数调用的相关信息。 一般的函数要到判断结束再逐层返回，尾递归到了底部就直接返回，因为有尾变量来保存值。 参考： https://blog.csdn.net/qq_51662208/article/details/135694199 原文出处：http://malaoshi.top/show_1GWK4GQrEem.html