尾遞歸和斐波那契

Question

我一直在尋找這個網站：http://rosettacode.org/wiki/Fibonacci_sequence#JavaScript，看到這個節目：

function fib(n) { 
    return function(n,a,b) { 
    return n>0 ? arguments.callee(n-1,b,a+b) : a; 
    }(n,0,1); 
} 

這是如何工作的，那些是什麼兩個參數（a和b）的幫助。我追查它，仍然不知道這是如何工作的

Answer 1

在function(n,a,b)，n作爲遞減計數器，ab存儲兩個連續的斐波那契數計算的下一個目的，所以當n達到0，你有a爲第n + 1個斐波那契數（因爲真正的斐波那契有兩個1作爲開始）。

例如，N = 4：

n a b 
4 0 1 
3 1 2 
2 2 3 
1 3 5 
0 5 8 

正如你可以看到，a的值和b總是等於斐波那契數。此外，這與函數式編程非常相似（如網站所述Scheme程序員）。

Answer 2

a和b是一個新定義的匿名函數的參數。

我會看看這個page這是關於arguments對象的文檔。從文檔中，arguments.callee是對當前函數的引用。必須這樣做，因爲它們使用匿名函數，所以它確實沒有名稱（他們知道）。

看起來好像它們遞歸調用它們（匿名）定義的深度爲n的函數。一路上，他們正在計算fib數，並且一旦深度達到n，他們就返回值a。傳遞到函數的初始值是(n,0,1)

Answer 3

至於解釋here，arguments.callee的指的是當前功能你在，既然你是在功能匿名，這是調用函數，實現遞歸的唯一途徑。

該特定函數通過在內部函數中遞歸調用來計算Fibonacci sequence。

Answer 4

a和b分別代表從0和1開始的序列的當前編號和下一個編號。 n是一個倒數計時器，用於指定返回斐波納契數列的哪個元素（EG：n = 10將返回55）。

此功能通過接受一個參數n這意味着它將計算該序列的第n號：

function fib(n) { 

然後，該代碼定義了一個函數，將所述序列中計算下一數：

function(n,a,b) { 
    return n>0 ? arguments.callee(n-1,b,a+b) : a; 
} 

基本上這個匿名函數在每次執行時倒數n，同時將a和b移動到t中的下一個數字他序列。如果n等於0，則序列完成並返回當前編號a。

arguments.callee引用當前正在執行的函數，所以代碼只是意味着用新的參數回調自己。換句話說，開始「循環」的下一次迭代。

最後，通過說(n,0,1);該代碼實際上調用fib與參數n,0,1。 return聲明 - 我從上面的代碼片段中刪除 - 採用匿名函數的返回值並將其返回給調用者fib。

---

也就是說，以這種方式使用遞歸對JavaScript等沒有尾部呼叫優化的語言來說是低效的。對於大型的n，你最好用標準循環結構來代替遞歸來寫。

Answer 5

我看到一些可能導致混淆的問題。遞歸函數模式的短手和尾部優化。

問題可能出在短代碼版本的代碼中。爲了清晰起見，請重新編寫。

1. 給它一個名字承認匿名函數「復發」
2. 條件（三元）運算符擴大。

尾部優化用於通過添加累加器部件來控制遞歸函數的堆棧使用。這是一種常見的模式，但會消除可讀性。這是重複函數。

特別說明，與循環迭代相比，性能非常好。

function fib(n) { 
 
    function recur(n, a, b) { 
 
     if (n > 0) { 
 
      return recur(n - 1, b, a + b); 
 
     } else { 
 
      return a; 
 
     } 
 
    } 
 
    return recur(n, 0, 1); 
 
}

關於參數，Ñ是迭代計數器，一個和b是斐波納契的序列部分。