起因

今天参加公司分享时，同事分享主题是WebWorker, 讲解demo过程中举例了一个计算量很大的斐波那契数列计算。突然就想到之前，面字节时被问到的递归改进方法，当时一脸懵逼。 后来查了一下是尾递归优化 。 当时本博客还没诞生， 现在想起来了就记录一下吧

尾调用

首先明白什么是尾调用

简而言之就是： 在函数的最后是调用另一个函数，并且不能是表达式

调用另一个函数

很好理解， 熟悉的柯里化就是调用另一个函数

不能是表达式

就是说必须是函数的签名调用 形如f(x) , 对于传参，如果不会形成闭包即可。

这两种情况就不是尾调用， 第一种情况，实际上是调用变量y 并不是所谓的调用另一个函数 ； 第二种情况， 实际上是执行一个表达式， 所以也不会进行尾调用优化。

为什么尾调用可以进行优化

我们都知道在A函数调用时会将A函数放入调用栈中，如果在A函数中存在另一个B函数调用，此时也会将B压入调用栈中，等待B函数调用完成后，此时才可以从调用栈中弹出A函数和B函数。那如果使用尾调用时，当执行A函数时，将A函数压入调用栈中，当执行A时发现存在B函数，并且B函数为A函数的最后一步调用，此时可以将A函数从调用栈中弹出，将B函数压入调用栈中。这样下来性能就做到了优化。

尾递归

函数调用自身，叫做递归。如果尾调用自身，则就称为尾递归。

一步一步想想如何尾递归

概念理解起来很简单， 但是当拿到递归代码时，如何将其改造为尾递归调用呢？

直接看最简单的例子 斐波那契数列

原始代码：

因为这里递归会存在许多的重复计算， 时间复杂度是O(n^2) 的。 并且按道理来说普通递归会持续维护一个调用栈，空间复杂度将是O(n) (但是在lc上执行发现内存消耗不高反而很低, 这一点我也没太明白，有无大佬解答一下)。代码非常质朴，执行用时也是非常的质朴.

首先想到时间复杂度这么高，空间复杂度这么低。 那么好 直接空间换时间吧， 加入一个滚动值表示上次计算的结果

第二版代码：

看看结果

果然时间直接差不多少了一半。

时间复杂度O(n) + 空间复杂度O(1) 这已经是比较好的版本了。

那么进入正题， 实现一个尾递归调用版的斐波那契数列。

思考既然尾调用只能调用函数，并且还是递归调用， 那么我们前一个状态只能通过参数传递给下一个状态。

而在第二版代码中， 是通过两个变量first和second来传递给下一次计算的。

那么就把first和second 变为参数传递给递归时的下一次计算吧

对比第二版代码：

第二版中

third = first + second 和 second = third 两步操作， 就等价于 return fib(n - 1, second, first + second);

相当于计算出当前的和并将其传递给下一次计算的second

first = second; 就等价于return fib(n - 1, second, first + second); 也就是把当前的second值，传递给下一次计算的first

对比第一版代码：

时间复杂度从O(n^2) 降到了O(n)

空间复杂度 我猜测如果尾调用优化生效的话应该是从O(n) 降到了O(1)

看看执行时间

可以发现实际上和第二版代码在时间和空间消耗上都差不多。

模拟过程

🦑注意 ！尾递归调用时，返回条件有所变化， 当 n 递减到 0 时，我们已经通过递归调用了 n 次，因此 first 正好表示的是数列中的第 n 个数。

假如要计算第10个斐波那契数

1. 初始调用:
   • n: 10
   • first: 0
   • second: 1

1. 第一次递归调用:
   • n: 9
   • first: 1
   • second: 1 (first + second)

1. 第二次递归调用:
   • n: 8
   • first: 1
   • second: 2 (first + second)

1. 第三次递归调用:
   • n: 7
   • first: 2
   • second: 3 (first + second)

1. 第四次递归调用:
   • n: 6
   • first: 3
   • second: 5 (first + second)

1. 第五次递归调用:
   • n: 5
   • first: 5
   • second: 8 (first + second)

1. 第六次递归调用:
   • n: 4
   • first: 8
   • second: 13 (first + second)

1. 第七次递归调用:
   • n: 3
   • first: 13
   • second: 21 (first + second)

1. 第八次递归调用:
   • n: 2
   • first: 21
   • second: 34 (first + second)

1. 第九次递归调用:
   • n: 1
   • first: 34
   • second: 55 (first + second)

1. 第十次递归调用:
   • n: 0
   • first: 55
   • second: 89 (first + second)

此时，n 等于 0，递归终止，返回 first 的值。

注意事项

根据阮一峰老师这篇文章下边的评论， 浏览器V8引擎已经是默认关闭了尾递归优化。

但是这仍然是一种优化思路。 尾递归这种思路确实感觉比普通的递归更难理解， 但是我们可以站在巨人的肩膀上前行（直接将递归函数扔给AI ^^!）

Prev

Docker、Nginx相关问题记录

Next

649. Dota2 参议院