斐波那契數(shù)列

斐波那契數(shù)列（Fibonacci sequence），又稱黃金分割數(shù)列、因數(shù)學(xué)家列昂納多·斐波那契（Leonardoda Fibonacci）以兔子繁殖為例子而引入，故又稱為“兔子數(shù)列”。

該數(shù)列由 0 和 1 開始，后面的每一項數(shù)字都是前面兩項數(shù)字的和。如：1 1 2 3 5 8 ..
計算公式：F(N) = F(N - 1) + F(N - 2) (N > 1)

尾遞歸

尾遞歸：尾調(diào)用的一種特殊情況，特別的是尾遞歸在最后一步調(diào)用自身。

使用遞歸時，必須給出終止條件，否則代碼將無限循環(huán)的執(zhí)行。

我們經(jīng)常使用諸如遞歸之類的方法來查找階乘等，但遞歸容易發(fā)生堆棧溢出的問題。

尾遞歸優(yōu)點：由于只存在一個調(diào)用棧，所以永遠不會出現(xiàn)“棧溢出”錯誤，節(jié)省內(nèi)存。

尾遞歸優(yōu)化的斐波那契數(shù)列

非尾遞歸Fibonacci序列實現(xiàn)如下：

function Fibonacci(n) {
    if (n <= 1) {
        return 1;
    }
    return Fibonacci(n - 1) + Fibonacci(n - 2);
}

尾遞歸優(yōu)化的Fibonacci序列實現(xiàn)如下：

function Fibonacci(n, ac1 = 1, ac2 = 1) {
    if (n <= 1) {
        return ac2;
    }
    return Fibonacci(n - 1, ac2, ac1 + ac2);
}

小小斐波那契數(shù)列常常被面試官偏愛，那接下來有時間會整理一下斐波那契數(shù)列算法優(yōu)化問題~