斐波那契數(shù)列遞歸算法？答:斐波那契數(shù)列遞歸算法是:在一列數(shù)中，從第三項(xiàng)開始，每項(xiàng)數(shù)等于和它相鄰的前面兩項(xiàng)數(shù)的和。用遞推式表示為:an 2=an 1 an(n≥1)尾遞歸究竟是好是壞？概念遞歸如果層次太

斐波那契數(shù)列遞歸算法？

答:斐波那契數(shù)列遞歸算法是:在一列數(shù)中，從第三項(xiàng)開始，每項(xiàng)數(shù)等于和它相鄰的前面兩項(xiàng)數(shù)的和。用遞推式表示為:an 2=an 1 an(n≥1)

尾遞歸究竟是好是壞？

概念

遞歸如果層次太多，就會照成棧溢出異常，因?yàn)槊空{(diào)用一次就會新生成一個棧幀，使用這個棧幀保留當(dāng)前函數(shù)的狀態(tài)值。如果沒有必要保存狀態(tài)值，那么就可以復(fù)用棧幀，不會造成棧溢出。

舉例

這里以求n的階乘舉例：

正常遞歸：

假如n=3；那么每一步都需要保留n值以及下一步函數(shù)的返回值，所以每次調(diào)用都需要創(chuàng)建一個新的棧幀

尾遞歸：

假如n=3，這里每一次調(diào)用是可以復(fù)用棧幀的，因?yàn)椴恍枰４鏍顟B(tài)值。

總結(jié)

所以說當(dāng)遞歸是在當(dāng)前棧幀執(zhí)行完之后，不需要再保留當(dāng)前棧幀，而是帶著當(dāng)前棧幀的結(jié)果，進(jìn)入到下一棧幀，就可以優(yōu)化為尾遞歸，一般尾遞歸需要滿足遞歸調(diào)用是函數(shù)體中最后執(zhí)行的語句。比如階乘的例子中最后執(zhí)行的語句是直接調(diào)用factorial(n-1， n*result)，而不是一個表達(dá)式n * factorial(n -1)，如果是表達(dá)式的話就需要一個棧幀來保留n和factorial(n -1)的結(jié)果。