如何可視化斐波納契遞歸？

Question

我總是努力想象遞歸，因爲它不像循環和循環這樣的迭代方法那麼簡單。

這是很容易失去跟蹤是怎麼回事，在遞歸，因爲我們經常與抽象的概念，工作就像值（數字）和變量（X & Y）的。

斐波那契數列的遞歸方法如何以可避免抽象的方式可視化並使用易於想象的隱喻？

Answer 1

遞歸的一個流行介紹是通過Fibonacci序列。

斐波背後的基本思路是這樣的：

Every number after the first two is the sum of the previous two numbers. 

1, 1, 2, 3, 5, 8, 13, 21... to Infinity 

我們可以看看這個問題反覆：

0 + 1 = 1 (1st) 
1 + 1 = 2 (2nd) 
1 + 2 = 3 (3rd) 
2 + 3 = 5 (4th) 
... 

在迭代0 & 1，斐波那契序列具有1.每個值迭代之後，我們只需將前兩個值加在一起返回2 ... 3 ... 5 ...等等。

這裏是迭代方法的一個JavaScript例如：

function fib(n) { 

    var prior  = 1, // sum of previous sequence 
     priorprior = 1, // sum before previous 
     sum   = 1; // sum of prior + priorprior 

    for (var i = 2; i <= n; i++) { 

     // get current fibonacci sequence value 
     sum = prior + priorprior; 

     priorprior = prior; 
     prior  = sum; 
    } 

    return sum; 
} 

遞歸接近從端這個問題。

它假定我們有以前的兩個值（2 & 3），我們只需要將它們加起來5

2 + 3 = 5 (4th) 

思考這個問題，我們可以想像，有一個微小的住在一個盒子裏的人。

他們有一個簡單的工作：

• 剛剛傳回1，如果數量爲1或更低。

• 添加前面的2個數字並將其總和返回。

在此框內，還有2個框：每個前面的斐波那契數列。

而在每個小盒子裏面，有更多的人在做同樣的簡單工作。

當我們要求第一個盒子裏面的人找到一個斐波那契數列時，他們會問他們的盒子是否爲前一個斐波那契數列，這樣他們就可以將它們相加。

小盒子裏面的人也會這樣做。

會發生此遞歸直到當問及斐波那契序列是1或0

那些人只需要傳回1。

一旦數字開始傳回，人們可以開始返回他們的金額，一直返回到我們的原始方塊。

我們的第一個盒子將簡單地總結他們回來的2個數字並將答案提交給我們。

這裏有一個例子，以幫助該可視化：

低效的遞歸JavaScript示例：

function fib(n) { 

    if (n <= 1) { 
     return 1; 
    } 

    // return sum of the previous 2 numbers 
    return fib(n - 1) + fib(n - 2); 
}