-2

再帰が「自分自身を呼び出すメソッド」であることは周知の事実ですが、実際には何が起こっているのか疑問に思う傾向があります。古典的な階乗の例を見てみましょう:

public static int fact(int n) {
    if(n == 0)
        return 1;
    else
        return n * fact(n - 1);
}

事実(5);

私はそれが次のようになることを理解しています:(等号は、その値に対して関数が呼び出されたときに何が起こっているかを示します)

http://postimg.org/image/4yjalakcb/

なぜ再帰はこのように機能するのですか? コンピューターのどの側面が、そのように逆方向に機能するのですか? 舞台裏で何が起こっているのですか？

学生として、私たちが教えられている再帰は浅く一般的なものだと感じています。ここの優れたコミュニティが、マシン自体のレベルでそれを理解するのに役立つことを望んでいます. ありがとうございました！

4

4 に答える 4

7

メソッドを呼び出すたびに何が起こるかの簡単な概要を次に示します。

  • そのメソッドのフレームがスタックから割り当てられます。
  • フレームには、すべてのローカル変数、パラメーター、メソッドの戻り値が含まれます。
  • そのフレームは、このメソッドを呼び出す現在のメソッドのフレームの上に配置されます。
  • メソッドが戻ると、そのメソッドに関連するフレームがスタックから取り出され、呼び出し元のメソッドが再び動作を開始し、前のメソッドからの戻り値があればそれを受け取ります。

フレームの詳細については、JVM Spec-Framesを参照してください。

再帰の場合、同じことが起こります。とりあえず、再帰を扱っていることを忘れて、各再帰呼び出しを別のメソッドの呼び出しと見なしてください。したがって、factorial場合によっては、スタックは次のように成長します。

fact(5)
  5 * fact(4)
    4 * fact(3)
      3 * fact(2)
        2 * fact(1) 
          1 * fact(0)  // Base case reached. Stack starts unwinding.
        2 * 1 * 1
      3 * 2 * 1 * 1
    4 * 3 * 2 * 1 * 1
  5 * 4 * 3 * 2 * 1 * 1  == Final result
于 2013-08-05T21:13:12.577 に答える
2

関数呼び出しをトレースすると、どのように機能するかがわかります。

例えば

fact(3)戻り3 * fact(2)ます。したがって、Java は を呼び出しますfact(2)。

fact(2)戻り2 * fact(1)ます。したがって、Java は を呼び出しますfact(1)。

fact(1)戻り1 * fact(0)ます。したがって、Java は を呼び出しますfact(0)。

fact(0)戻り1ます。

その後、fact(1)戻り1 * 1 = 1ます。

その後、fact(2)戻り2 * 1 = 2ます。

その後、fact(3)戻り3 * 2 = 6ます。

Java は、他のメソッドと同じように再帰メソッドを呼び出します。

于 2013-08-05T21:11:13.680 に答える
0

たぶん、以下があなたを理解するのに役立つでしょう。コンピューターは、計算しているだけの関数と同じ関数を呼び出すかどうかは気にしません。再帰とは何か、リストや自然数など、それ自体が構造によって再帰的である多くのもので機能する理由を理解すれば、再帰に魔法のようなものは何もありません。

  1. 定義: 0 の階乗は 1 です
  2. 定義: 0 より大きい数 n の階乗は、その数とその前の階乗の積です。

したがって

5! = 5*4! = 5*4*3! = 5*4*3*2! = 5*4*3*2*1! = 5*4*3*2*1*0! = 5*4*3*2*1*1 = 120

したがって、帰納法による証明について聞いたことがある場合は、次のようになります。

  1. 基本ケースのいくつかのプロパティを証明します。
  2. この性質が n に対して真であれば、n の後継者に対しても真であることを証明します。
  3. これは、基本ケースと後続のすべてのケースでプロパティが保持されることの証明であると結論付けます。

例：偶数の二乗は4の倍数であることを帰納法で証明！

  1. 0 の 2 乗は 0 で、4 の倍数です。
  2. n を偶数とし、その二乗 n² は 4 の倍数(2+n)*(2+n)です4+2n+2n+n²。これは 4 の倍数です。なぜなら、n² は仮定によるものであり、4 は 1 であり、2n+2n = 4n4 の倍数でもあり、4 の倍数の和は分配法則により 4 の倍数だからです。4a + 4b = 4(a+b)
  3. QED このプロパティは、0 (基本ケース) に対して保持され、n に対して保持される場合は (2+n) に対して保持されます。したがって、2、4、6、8 .... およびその他すべての偶数に適用されます。

(2a)²(より簡単な証明は、4 の倍数である=を観察すること4*a*aです。)

再帰的なプログラムを書くことは、帰納法による証明をすることに非常に似ています:

  1. ベースケースの計算を書きます。
  2. 非基本ケースの場合、結果を計算する方法はわかっています (たとえば、 がわかっているn! = n * (n-1)!ので、必要な関数は今書いている関数なので、 だけ書き留めます!
  3. このプログラムは、ベース ケースとベース ケースの後続ケースの正しい値を計算すると結論付けることができます。678!それでも正しい答えが計算されない場合intは、大きな数にはあまり適していないようなデータ型を使用したという事実に関係しています (または、別の言い方をすれば、すべてを 2^32 ムーロで計算します)。さらに、使用可能な数値の半分を負の数値として解釈することを主張するソフトウェアを使用します。

これが機能する理由は、コンピューターのハードウェアやプログラミング言語とは関係ありません。前に述べたように、アイテム (リスト、ツリー、セット、自然数) の再帰的な構造の結果です。

初心者がよく犯す間違いは、基本的なケースを無視して複雑さに惑わされることです。基本的なケースから始めることを常にお勧めします。これがあれば、関数が存在すると仮定して、より複雑なケースで使用することができます。

于 2013-08-05T22:24:57.770 に答える