フィボナッチ再帰を視覚化するには？

Question

whileループやforループなどの反復アプローチほど簡単ではないので、私は再帰を視覚化するために常に苦労しています。

ほとんどの場合、値（数値）や変数（x & y）などの抽象概念で作業するため、再帰で何が起こっているのかを簡単に追跡できます。

フィボナッチシリーズへの再帰的アプローチは、抽象化を避け、想像しやすいメタファを使用する方法でどのように視覚化できますか？

Answer 1

再帰の一般的な紹介は、フィボナッチシーケンスによるものです。

はフィボナッチの背後にある基本的な考え方はこれです：

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で

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

、フィボナッチ数列は、1。各値を持っています繰り返しの後に、前の2つの値を加算して、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つの数値を加算し、合計を戻します。

このボックスの中には、前のフィボナッチシーケンスごとに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); 
}