4

末尾再帰の例を見つけようとしましたが、通常の再帰と末尾の違いが本当にわかりません。これが末尾再帰でない場合、誰かが理由を教えてもらえますか?

public static long fib(long index) {

// assume index >= 0

if (index == 0) // Base case

  return 0;

else

  if (index == 1) // Base case

    return 1;

  else

    // Reduction and recursive calls

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

}  // end of method fib(long index)
4

2 に答える 2

16

いいえ、問題の方法は末尾再帰を使用しません。末尾再帰は簡単に認識できます。再帰ステップは、メソッドで発生する最後のことです。

コードでは、両方の再帰呼び出しが終了した後、実行する操作がもう 1 つあります。追加です。したがって、メソッドはrecursiveですが、末尾再帰ではありません。

比較のために、fib()メソッドの末尾再帰実装を次に示します。再帰の状態を保存するために追加のパラメーターを渡す必要があることに注意してください。さらに重要なことに、再帰呼び出しが返された後に行う操作が残っていないことに注意してください。

public static long fib(int n, long a, long b) {
    return n == 0 ? b : fib(n-1, a+b, a);
}

次のように使用します。

fib(10, 1, 0) // calculates the fibonacci of n=10
=> 55

以前の実装は n=92 までは問題なく動作し、より大きな数の場合はBigIntegerの代わりに使用する必要がlongあり、反復アルゴリズムに切り替えることをお勧めします。

于 2013-09-03T00:19:47.657 に答える
4

@Óscar López が質問に答えました。

呼び出しがテール コールかどうかを知ることに人々が関心を持つ理由は、テール コールを分岐に置き換えることができる最適化があるためです。これにより、新しいスタック フレームを作成する必要がなくなります。これにより、制限付きスタックで無制限の末尾再帰が可能になります。

ただし、質問に のタグを付けたjavaので、現在の Java 実装は末尾呼び出しの最適化を実装していないことを知っておく必要があります。Java で深く再帰的なメソッド呼び出しを行うと、StackOverflowError.

于 2013-09-03T01:29:38.613 に答える