线性递推式问题-斐波那契数列
文章目录
1、递归
function Fibonacci(n) {
if (n === 1 || n === 2) {
return 1
}
return Fibonacci(n-1) + Fibonacci(n-2)
}
递归最大的问题就是当调用帧过多时导致内存溢出
2、闭包-把运算结果存储在数组里,避免重复计算
function Fibonacci(n) {
let arr = [0, 1] // 把计算过的结果存储在数组里
return (n) => {
if (arr[n] === undefined) {
arr[n] = Fibonacci(n-1) + Fibonacci(n-2)
}
return arr[n]
}
}
3、循环
function Fibonacci(n) {
let res1 = 1
let res2 = 2
if (n === 1 || n === 2) {
return res2
}
for(let i = 3; i <= n; i++) {
[res1, res2] = [res2, res1 + res2]
}
return res2
}
4、尾调用
尾调用之所以与其他调用不同,就在于它的特殊的调用位置。
我们知道,函数调用会在内存形成一个“调用记录”,又称“调用帧”(call frame),保存调用位置和内部变量等信息。如果在函数A的内部调用函数B,那么在A的调用帧上方,还会形成一个B的调用帧。等到B运行结束,将结果返回到A,B的调用帧才会消失。如果函数B内部还调用函数C,那就还有一个C的调用帧,以此类推。所有的调用帧,就形成一个“调用栈”(call stack)。
尾调用由于是函数的最后一步操作,所以不需要保留外层函数的调用帧,因为调用位置、内部变量等信息都不会再用到了,只要直接用内层函数的调用帧,取代外层函数的调用帧就可以了。
详情参阅函数扩展之尾调用优化——阮一峰。
function Fibonacci(n, res1 = 1, res2 = 1) {
if (n <= 2) {
return res2
}
return Fibonacci(n-1, res2, res1 + res2)
}
5、矩阵相乘-解决线性递推式问题
参考:
https://www.cnblogs.com/zkfop...
https://www.cnblogs.com/super...
https://blog.csdn.net/qq_3930...
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论