面试被问尾递归优化知道怎么做吗？

递归本质上也是一种函数循环，在函数里对自身的一种调用，在一些常用的数据结构二叉树、图等会用到递归进行遍历、搜索，本节讲的是在普通递归基础之上的尾递归优化。

在 “Nodejs技术栈” 交流群上有童鞋提到在之前面试中有被问到 “尾递归” 这一问题，另外之前也刚写过二叉搜索树，用到了大量的递归来实现，所以也顺便讲解下什么是尾递归相比普通的递归调用有什么优势。

什么是尾递归呢？

调用者在调用一个递归函数并取得返回值之后，不在进行其它计算，直接返回！有什么好处呢？

“在程序运行时，计算机会为应用程序分配一定的内存空间；应用程序则会自行分配所获得的内存空间，其中一部分被用于记录程序中正在调用的各个函数的运行情况，这就是函数的调用栈。常规的函数调用总是会在调用栈最上层添加一个新的堆栈帧（stack frame，也翻译为“栈帧”或简称为“帧”），这个过程被称作“入栈”或“压栈”（意即把新的帧压在栈顶）。当函数的调用层数非常多时，调用栈会消耗不少内存，甚至会撑爆内存空间（栈溢出）[1]，造成程序严重卡顿或意外崩溃。尾调用的调用栈则特别易于优化，从而可减少内存空间的使用，也能提高运行速度。[1]其中，对尾递归情形的优化效果最为明显，尤其是递归算法非常复杂的情形。—— 维基百科”

看完这些概念会很晦涩，还是难以理解，下面让我们通过一个简单的阶乘例子彻底弄清楚它。

求 N 的阶乘

任何大于 1 等于 1 的自然数阶乘公式为：n! = 1 * 2 * 3 * (n -1)n

普通的递归调用

下面这个例子中，拿到尾部 factorial() 返回值之后QQ号卖号平台没有直接返回，而是又做了一次乘法运算，那么这就不是一个尾递归。

function factorial(n) { if (n === 1) { return n; } return n * factorial(n - 1) // 重点在尾部调用返回 } console.log(factorial(5)) // 120 复制代码

它的执行过程如下所示：

factorial(5) 5 * factorial(5 - 1) 5 * 4 * factorial(4 - 1) 5 * 4 * 3 * factorial(3 - 1) 5 * 4 * 3 * 2 * factorial(2 - 1) 5 * 4 * 3 * 2 * 1 5 * 4 * 3 * 2 5 * 4 * 6 5 * 24 120 // 结果复制代码

尾递归优化

我们使用了 ES6 函数默认值，是为了 factorial() 初次调用时仅传入一个值，代码示例如下：

function factorial(n, total = 1) { if (n === 1) { return total; } return factorial(n - 1, total * n); // 重点在尾部调用返回 } console.log(factorial(5)) // 120 复制代码

上面这种就是尾递归调用的写法，在拿到 factorial(n - 1, total * n) 返回值后，直接返回！它的执行过程如下所示：

factorial(5) factorial(4, 5) factorial(3, 20) factorial(2, 60) factorial(1, 120) 复制代码

通过上面普通递归、尾递归优化之后的执行过程分析也很清晰了，优化之前的递归调用它的调用链条会不断的加强，相比优化之后的会更消耗资源。

Reference

zh.wikipedia.org/wiki/尾调用

更多相关文章

随机推荐