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

面试被问尾递归优化知道怎么做吗?_第1张图片

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

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

什么是尾递归呢?

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

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

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

求 N 的阶乘

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

普通的递归调用

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

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)

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

推荐阅读

1、你不知道的前端异常处理(万字长文,建议收藏)

2、你不知道的 TypeScript 泛型(万字长文,建议收藏)

3、lucifer与它的《力扣加加》来啦

4、你不知道的 React 最佳实践

5、或许是一本可以彻底改变你刷 LeetCode 效率的题解书

6、用TypeScript编写React的最佳实践

7、vite —— 一种新的、更快地 web 开发工具

关注加加,星标加加~

如果觉得文章不错,帮忙点个在看呗

你可能感兴趣的