JS 斐波那契数列的三种算法实现

斐波那契数列

形如1,1,2,3,5…的数列就是斐波那契数列。其通项fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)。

递归算法

var numbers = [];
function fibonacciRecursion(n) {
    if (numbers[n] !== undefined) {
        return numbers[n];
    }
    if (n === 1 || n === 2) {
        numbers[n] = 1;
    } else {
        numbers[n] = fibonacciRecursion(n - 1) + fibonacciRecursion(n - 2);
    }
    return numbers[n];
}

思路：使用numbers[n]记录序号为n的数列项值，避免多次运算。递归调用函数实现通项公式。

问题：n值过大时会出现函数调用栈溢出的情况。

迭代算法

function fibonacciLoop(n) {
    var result = 0,
        former = 1,
        temp = 0;
    for (var i = 1; i <= n; i++){
        if (i <= 2) {
            result = 1;
        } else {
            temp = result;
            result += former;
            former = temp;
        }
    }
    return result;
}

思路：定义3个变量，result保存febonacci(n-1)，former保存febonacci(n-2),temp作为临时变量保存交换前的数据。在下一次循环中将两个值相加得febonacci(n)。

问题：代码量大，不够简洁。

尾递归

尾递归指函数最后的返回值只有一个函数，不包括任何运算符。

function fibonacciTail(n,former,result) {
    "use strict";
    if (n === 1 || n === 2) {
        return result;
    }
    return fibonacciTail(n - 1, result, former + result);
}

思路： 事实上思路与迭代一致，将迭代中的变量转变为形参，这样还省去了temp变量。同时不需要担心递归调用导致的栈溢出，因为函数每次执行到最后相当于将当前函数出栈，新函数入栈。

问题： 仅ES6的严格模式下支持尾递归优化。