11

コード1：

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

fibonacciそれがまだ何であるかを説明し終えていない場合、どのように使用できますか？私はこのような他の場合に再帰を使用することを理解することができました：

コード2：

class two 
{
    public static void two (int n) 
    {
        if (n>0) 
        {
            System.out.println (n) ;
            two (n-1) ;
        }
        else
        {
            return ;
        }
    } 

    public static void main (String[] arg) 
    {
        two (12) ;
    }
}

ただし、コード2の場合、n最終的にはそれが満たされないポイントに到達しn>0、メソッドは再帰的にそれ自体を呼び出すのを停止します。n=1ただし、コード2の場合、開始点が2、3、5などの場合、1からどのように取得できるかわかりません。また、機能するためにはある意味で含まれている必要があるreturn fibonacci (n-1) + fibonacci (n-2)ため、行がどのように機能するかはわかりませんが、まだ存在していません。fibonacci (n-2)fibonacci (n-1)

私が見ている本はそれがうまくいくと言っています。それはどのように機能しますか？

4

9 に答える 9

12

コンパイラがコードに対して実際に行うこと (恐ろしいことですが、美しい) と、CPU がコードを実際にどのように解釈するか (同様に) は別として、かなり単純な解決策があります。

次のテキストの指示を検討してください。

番号付きブロックをソートするには:

  1. ランダムなブロックを選択します。
  2. それが唯一のブロックである場合は、停止します。
  3. 数字の小さいブロックを左側に、数字の大きいブロックを右側に移動します。
  4. 番号の小さいブロックを並べ替えます。
  5. 番号の大きいブロックを並べ替えます。

手順 4 と 5 に到達すると、プロセス全体を最初からやり直すよう求められます。ただし、プロセスの開始方法はまだわかっているので、これは問題ではありません。最終的にすべてがうまくいくと、ソートされたブロックの束が得られます。指示を紙片で覆うことができ、従うのが難しくありません。

于 2010-03-09T05:22:45.930 に答える
3

コード 2 の場合、n は最終的に n>0 を満たさないポイントに到達し、メソッドは再帰的に自分自身を呼び出すのを停止します。

似ているようにするには、条件if (n == 0 || n == 1)を次のように置き換えることができますif (n < 2)

また、「return fibonacci (n-1) + fibonacci (n-2)」という行がどのように機能するかわかりません。なぜなら、fibbonacci n-2 は、機能するために何らかの意味で fibonacci n-1 を含まなければならないからです。まだあります。

「フィボナッチn -1は何らかの意味でフィボナッチ n-2 を含まなければ
ならないので」再帰レベルごとに 2 回 (例ではfibonacci(1) ): 1.現在のステップでfibonacci (n-2)を 実行するとき 2.次のステップで fibonacci ((n-1)-1)を実行するとき

（スパイクのコメントもよく見てください）

fibonacci(3)を呼び出すと仮定すると、 fibonacciの呼び出しスタックは次のようになります: (Veer はより詳細な説明を提供しました)

n=3。フィボナッチ(3)  
n=3。fibonacci(2) // fibonacci(n-1) の呼び出し
   n=2。fibonacci(1) // fibonacci(n-1) の呼び出し
      n=1。1 を返します
   n=2。fibonacci(0) // fibonacci(n-2) の呼び出し
      n=0。1 を返します
   n=2。加算して 2 を返す
n=3。fibonacci(1) //fibonacci(n-2) の呼び出し
   n=1。1 を返します
n=3。合計し、2 + 1 を返します

fibonacci(n)での加算は、小さい引数のすべての関数が返された後にのみ行われることに注意してください (つまり、 fibonacci(n-1)、fibonacci(n-2) ... fibonacci(2)、fibonacci(1)、fibonacci( 0) )

より大きな数の呼び出しスタックで何が起こっているかを確認するには、次のコードを実行できます。

public static String doIndent( int tabCount ){
    String one_tab = new String("   ");
    String result = new String("");
    for( int i=0; i < tabCount; ++i )
       result += one_tab;
    return result;
}

public static int fibonacci( int n, int recursion_level )
{
    String prefix = doIndent(recursion_level) + "n=" + n + ". ";

    if (n == 0 || n == 1){
        System.out.println( prefix + "bottommost level, returning 1" );
        return 1;
    }
    else{
        System.out.println( prefix + "left fibonacci(" + (n-1) + ")" );
        int n_1 = fibonacci( n-1, recursion_level + 1 );

        System.out.println( prefix + "right fibonacci(" + (n-2) + ")" );
        int n_2 = fibonacci( n-2, recursion_level + 1 );

        System.out.println( prefix + "returning " + (n_1 + n_2) );
        return n_1 + n_2;
    }
}

public static void main( String[] args )
{
    fibonacci(5, 0);
}
于 2010-03-09T07:13:58.160 に答える
2

トリックは、 fibonacci() への呼び出しが返されるまで、 fibonacci() への最初の呼び出しが返されないことです。

n == 0 || の基本ケースに到達するまで、スタック上の fibonacci() への呼び出しに次ぐ呼び出しが発生し、どれも返されません。n == 1. この時点で、fibonacci() 呼び出しの (潜在的に巨大な) スタックが、最初の呼び出しに向かって巻き戻され始めます。

いったん頭に浮かんだら、スタックがオーバーフローするまで、それは一種の美しいものです。

于 2010-03-09T05:27:49.653 に答える
2

「フィボナッチが何であるかをまだ説明していない場合、どのようにフィボナッチを使用できますか?」

これは、再帰を疑問視する興味深い方法です。ここに答えの一部があります: フィボナッチを定義している間、それはまだ定義されていませんが、宣言されています。コンパイラは、フィボナッチと呼ばれるものがあり、それが int -> int 型の関数であり、プログラムが実行されるたびに定義されることを認識しています。

実際、再帰的な識別子だけでなく、C プログラムのすべての識別子がこのように機能します。コンパイラは、何が宣言されているかを判断し、それらの使用を実際の場所に向けてプログラムを調べます (大幅に単純化しすぎています)。

于 2010-03-09T05:28:14.307 に答える
2

n=3 を考慮して実行をウォークスルーしましょう。それが役に立てば幸い。

n=3 の場合 => 条件が失敗し、そうでなければ実行される場合

return fibonacci (2) + fibonacci (1);

ステートメントを分割します。

  1. fibonacci(2) の値を求める
  2. fibonacci(1) の値を見つける
    // これは fib(n-2) ではなく、実行に fi​​b(n-1) を必要としないことに注意してください。独立しています。これはステップ 1 にも当てはまります。
  3. 両方の値を加算
  4. 合計値を返す

実行方法 (上記の 4 つの手順を拡張):

  1. fibonacci(2) の値を求める

    1. 失敗した場合、そうでない場合は実行します
    2. フィボナッチ(1)
      1. 実行する場合
      2. 値 '1' がステップ 1.2 に返されます。コントロールはステップ 1.3 に進みます。
    3. フィボナッチ(0)
      1. 実行する場合
      2. 値「1」はステップ 1.3 に返されます。コントロールはステップ 1.4 に進みます。
    4. 両方追加
      1. sum=1+1=2 //ステップ 1.2.2 から。および 1.3.2。
    5. return sum // 値 '2' がステップ 1 に返され、制御はステップ 2 に進みます

  2. fibonacci(1) の値を求める

    1. 実行する場合
    2. 値「1」が返されます

  3. 両方の値を加算

    1. sum=2+1 //ステップ 1.5 から。そして2.2。
  4. 合計値を返す //sum=3
于 2010-03-09T08:53:05.897 に答える
1

自分でイラストを描いてみてください。最終的にはどのように機能するかがわかります。return関数呼び出しが行われると、最初にその値がフェッチされることを明確にしてください。単純。

于 2010-03-09T05:17:43.303 に答える
1

デバッグを試し、ウォッチを使用して変数の状態を知る

于 2010-03-09T05:22:45.197 に答える
1

再帰を理解するには、呼び出しスタックがどのように機能するか、つまり関数が互いにどのように呼び出すかを知る必要があります。
関数が n==0 または n==1 の場合に停止する条件を持たない場合、関数は自分自身を再帰的に永久に呼び出します。最終的に関数がペタリングして 1 を返すため、これは機能します。その時点で、リターン フィボナッチ (n-1) + フィボナッチ (n-2) も値とともに返され、コール スタックが実際にクリーンアップされます。早く。

于 2010-03-09T05:28:31.040 に答える
0

そのコードを実行するときに PC が何をしているのかを例を挙げて説明します。

あなたが非常に大きな部屋に立っていると想像してください。この部屋の隣の部屋には大量の紙とペンとテーブルがあります。それではフィボナッチ(3)を計算してみましょう:

テーブルを取り、部屋のどこかに置きます。テーブルの上に紙を置き、「n=3」と書きます。次に、「うーん、3 は 0 と 1 ですか?」と自問します。答えはノーなので、「return fibonacci (n-1) + fibonacci (n-2);」とします。

ただし、問題があります。「フィボナッチ (n-1)」と「フィボナッチ (n-2)」が実際に何をするのかわかりません。したがって、さらに2つのテーブルを取り、元のテーブルの左右に配置し、両方に「n = 2」と「n = 1」と書かれた紙を置きます。

左の表から始めて、「2 は 0 に等しいか、それとも 1 に等しいか?」と考えます。もちろん、答えはノーなので、このテーブルの隣に「n=1」と「n=0」の 2 つのテーブルをもう一度配置します。

まだフォローしていますか？お部屋はこんな感じです。

n=1

n=2 n=3 n=1

n=0

「n=1」のテーブルから始めます。1 は 1 に等しいので、実際に何か有用なものを返すことができます! 別の紙に「1」と書き、「n=2」の表に戻ります。紙をテーブルに置き、別のテーブルで何をするかまだわからないので、別のテーブルに行きます。

もちろん「n=0」も1を返すので、紙にそれを書いて、n=2の表に戻ってそこに紙を置きます。この時点で、このテーブルには "n=1" と "n=0" のテーブルの戻り値を持つ 2 つの論文があり、このメソッド呼び出しの結果は実際には 2 であると計算できます。それを紙に書いて、「n=3」と書かれたテーブルの上に置きます。

次に、「n=1」が書かれたテーブルの右端まで行き、すぐに紙に 1 を書き、「n=3」が書かれたテーブルに戻します。その後、最終的に fibonacci(3) が 3 を返すと言うのに十分な情報が得られます。

あなたが書いているコードはレシピにすぎないことを知っておくことが重要です。コンパイラが行うのは、そのレシピを PC が理解できる別のレシピに変換することだけです。次のように、コードが完全に偽物である場合:

    public static int NotUseful()
    {
        return NotUseful();
    }

単に無限にループするか、私の例のように、実際にはどこにも役に立たないまま、ますます多くのテーブルを配置し続けます。コンパイラは、 fibonacci(n-1) または fibonacci(n-2) が実際に何をするかを気にしません。

于 2010-03-10T01:26:27.490 に答える