フィボナッチ（n）のこの実装はどのように機能しますか？ [再帰]

Question

は、Java帳から運動をTheresの私はそれは私が混乱している読んでいる：

Aフィボナッチ数列は、番号1、1、2、3、5、8、 13のシーケンスであり、 21,34などがあり、各番号（3番目の番号から）は前の2つの合計である です。 引数として整数をとり、 から始まる多くのフィボナッチ数を表示するメソッドを作成します。例えば、あなたが出力されます（フィボナッチは クラスの名前です）は、Javaフィボナッチ5を実行し、場合：1、1、2、3、5

私はそれが必要になることを誓ったかもしれません配列または前の数字を格納するいくつかの方法が、私は答えを見たとき、そうではありませんでした：

import java.util.*; 

public class Fibonacci { 

    static int fib(int n) { 
     if (n <= 2) 
       return 1; 

     return fib(n-1) + fib(n-2); 
    } 
    public static void main(String[] args) { 
    // Get the max value from the command line: 
    int n = Integer.parseInt(args[0]); 
    if(n < 0) { 
     System.out.println("Cannot use negative numbers"); return; 
    } 
    for(int i = 1; i <= n; i++) 
     System.out.print(fib(i) + ", "); 
    } 
} 

は、誰かが自分自身がこれを生成内の関数を使ってどのように説明できるだろうか？

Answer 1

コードはrecursiveの例です。関数が初めて呼び出されると、その関数が呼び出されるまで実行されます。その状態はスタックに格納され、コードは新しい入力データで再度実行を開始します。このプロセスは、入力が2未満になるまで繰り返され、ポイント1が返され、答えは前の呼び出し元に戻ります。例えば

、以下の実行中の（5）の結果、FIBを呼び出す：あなたは部分的に正しい

fib(5): 
    fib(4): 
     fib(3): 
      fib(2): 1 
      fib(1): 1 
     fib(2): 1 
    fib(3): 
     fib(2): 1 
     fib(1): 1 

注意。中間結果は、このソリューションのstackに保存されます。それが再帰的な解決策が非常に高価な理由の1つです。もう1つはその複雑さであるO(2^n)です。ただし、Fibonacci(n)を反復して保存することはできません。すべて前の結果あなたが本当に必要とするのは、最後の結果を保存し、1から数えてnまで数えることです。

Answer 2

これは再帰的な解決策です。再帰関数は、与えられた停止条件が満たされるまで自身を呼び出します。その後、各コールは、最初のコールだけが残るまで終了します。その最初の呼び出しが結果を出力します。あなたの解決策では

、停止条件がある。この条件が満たされるまで

if (n <= 2) 
      return 1; 

、関数は自分自身への連続呼び出しを行います。各呼び出しは、渡されたintをパラメータとして減らします。 2に達すると、関数は値1（fibonacci（n）のn = 1とn = 2の結果）を返すことを指示します。私が言ったよう

フィボナッチは、最後の2つの数の和、関数の再帰的な部分であるため、

return fib(n-1) + fib(n-2); 

は、（最後の二つの数字をN-1およびN-2との和を行います）。 nが2に等しいとき、関数fibへのこれらの呼び出しは最終的に値を持ち、返されます。

例：n = 3の場合、再帰部分はfib（2）とfib（1）を呼び出し、両方とも2以下であるため、両方の呼び出しが1を返します。したがって、printfは1、 2。 2は1 + 1の合計です（わかりますが、時には明らかに役立ちます）。

Answer 3

recursive functionの標準例です。

Fibonacci Numbersも再帰的に宣言されます。

両方fib(1)とfib(2)は、他のすべてがそうfib(3)=fib(2)+fib(1)、最後の二つのフィボナッチ数を加算して算出されている1として宣言されています。

は、まさにこのない計算方法にこれを比較し：ところで

static int fib(int n) { 
    if (n <= 2) 
      return 1; 

    return fib(n-1) + fib(n-2); 
} 

を、この2つの変数を使用して、フィボナッチ数を計算するための非常に遅い方法です（あなたはそれらのすべてを必要としません最後の2つのみ）、ループがO（n）にある場合、上記の再帰関数はO（2^n）回の演算を行います。

Answer 4

      F(n) 
          / \ 
         F(n-1) F(n-2) 
         / \ / \ 
        F(n-2) F(n-3) F(n-3) F(n-4) 
       / \ 
       F(n-3) F(n-4) 

重要な点は、このアルゴリズムは前回計算された数値の結果を保存しないため指数関数である点です。例えばF（n-3）は3回呼ばれる。詳細は、自身の中の関数を使用してDasguptaさんの章0.2