複数の返信を伴う再帰の混乱

Question

私はまだ再帰の周りに自分の心をラッピングしており、私は階乗のような基本的なものを得ると思います。フィボナッチは、（N-1）完全にダウン行く前に、通じ再発ん、return文で

/** 
* @param n >= 0 
* @return the nth Fibonacci number 
*/ 
public static int fibonacci(int n) { 
    if (n == 0 || n == 1) { 
     return 1; // base cases 
    } else { 
     return fibonacci(n-1) + fibonacci(n-2); // recursive step 
    } 
} 

：return文は、もう少し複雑なように次のコードであるときしかし、私はさらに明確化したいと思いますフィボナッチ（n-2）ステップ（それは理にかなっていますか？）もしそうなら、これは想像するのが非常に難しいようです。

Answer 1

はい、1つの呼び出しは、他の呼び出しが実行を開始する前にすべて終了して戻ります。

Javaでの呼び出しの順序は、よく定義されています。fibonacci(n-1)は、fibonacci(n-2)より前になります。

編集：質問がもともと含まれているので、[C++]タグは、ここにあるC++の物語の一部：2つの呼び出しのいずれかがまだもう一つの実行を開始する前に完了する必要がありますが、その1、fibonacci(n-1)かfibonacci(n-2)は、指定されていません。

この関数には副作用がないため、2つの呼び出しのうち最初に実行される呼び出しは問題ではありません。再帰の理解に重要なのは、現在のレベルでの呼び出しが戻る前に、両方の呼び出しを完了し、その結果を一緒に追加する必要があることだけです。

Answer 2

それは、このように動作します：

フィボナッチプログラム：

public int fibonacci(int n) { 
    if(n == 0) 
     return 0; 
    else if(n == 1) 
     return 1; 
    else 
     return fibonacci(n - 1) + fibonacci(n - 2); 
} 

説明：フィボナッチ数列で 各項目は、前の2の合計です。したがって、再帰アルゴリズムごとに。だから、

、

fibonacci(5) = fibonacci(4) + fibonacci(3) 

fibonacci(3) = fibonacci(2) + fibonacci(1) 

fibonacci(4) = fibonacci(3) + fibonacci(2) 

fibonacci(2) = fibonacci(1) + fibonacci(0) 

は今、あなたはすでにfibonacci(1)==1 and fibonacci(0) == 0を知っています。したがって、後で他の値を計算することができます。今

、

fibonacci(2) = 1+0 = 1 
fibonacci(3) = 1+1 = 2 
fibonacci(4) = 2+1 = 3 
fibonacci(5) = 3+2 = 5 

Answer 3

それははるかに違う自体よりも別の関数を呼び出すよりもではありません。呼び出し関数が結果を使って何かを行う前に終了する必要があります。

finobacci(0); // ==> 1 (since n is zero, the base case is to return 1) 
fibonacci(1); // ==> 1 (since n is one, the base case is to return 1) 

今基本ケースではありませんどの2を試すことができます：

fibonacci(2);    // == (since it's not the base case) 
fibonacci(1) + fibonacci(0); // == (both calls to fibonacci we already haver done above) 
1 + 1      // ==> 2 

だから現実に何が起こるかは、コールがフィニッシュには、2つの再帰呼び出しの各ながら待機をfibonacci2することで、単にSystem.out.printlnを実行する関数のように、次の行に進む前に引数を表示するまで待機します。再帰はそれほど特別ではありません。

トリビア：これはフィボナッチ自身からのオリジナルシリーズです。現代の数学者は、nでシリーズを開始し、ではなく、0, 1, 1, 2, ...のベースケースの結果としています。

Answer 4

複数の再帰では、基本ケースに達するまで、最初の呼び出しでプログラムが呼び出されます。この場合、fibonacci（n-1）;その後、再帰が停止し、再帰の第2部分に値を呼び出すように値を返しますfibonacci（n-2）。

プログラムで複数の再帰を視覚化しない場合は、 fibonacci recursion treeが役に立ちます。