尾递归优化的斐波那契数列
2019-04-08 本文已影响1人
番茄沙司a
斐波那契数列
斐波那契数列(Fibonacci sequence),又称黄金分割数列、因数学家列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”。
该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。如:1 1 2 3 5 8 ..
计算公式:F(N) = F(N - 1) + F(N - 2)
(N > 1)
尾递归
尾递归:尾调用的一种特殊情况,特别的是尾递归在最后一步调用自身。
当我们使用递归时,必须给出终止条件,否则我们将无限循环的执行。
我们经常使用诸如递归之类的方法来查找阶乘等,但递归容易发生堆栈溢出的问题。
尾递归优点:由于只存在一个调用栈,所以永远不会出现“栈溢出”错误,节省内存。
尾递归优化的斐波那契数列
非尾递归Fibonacci序列实现如下:
function Fibonacci(n) {
if (n <= 1) {
return 1;
}
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
尾递归优化的Fibonacci序列实现如下:
function Fibonacci(n, ac1 = 1, ac2 = 1) {
if (n <= 1) {
return ac2;
}
return Fibonacci(n - 1, ac2, ac1 + ac2);
}
小小斐波那契数列常常被面试官偏爱,那接下来有时间会整理一下斐波那契数列算法优化问题~🍋