フィボナッチ数列では、同じメソッドを 2 回再帰的に呼び出す従来の実装を見てきました。
public void fibonacci(int i)
{
fibonacci(1) + fibonacci(2);
}
この方法は、私が見たものや問題を解決する正しい方法の正確なコピーではありませんが、上記のように2つの方法が一緒に追加されているのを見ました. したがって、メソッドは再帰的に呼び出されませんが、再帰的に 2 回呼び出されます。C# でこのようなコードを記述すると、具体的にはどうなるでしょうか。2 つのメソッドは別々のスレッドで実行されますか? ボンネットの下で何が起こっているのですか？
いいえ、次々と呼ばれます。明示的に要求しない限り、追加のスレッドは作成されません (System.Threading などを使用)。呼ばれる順番は定かではありませんが、左から右の順だと思います。C#仕様には間違いなく含まれています。
これは、コンピューターがそれを行う方法について考えることが役立つときの 1 つです。
関数から始めましょう。LANGUAGE のことを少し考えないようにしてほしいので、Python 風味の疑似コードで記述します。
def fib(n):
if n == 0: return 0
if n == 1: return 1
if n > 1: return fib(n-2) + fib(n-1)
それでは、fib(2) について説明しましょう。
fib(2)n>1であるため、3 番目のブランチを使用します。
return fib(2-2) + fib(2-1)
したがって、0 でfib()を呼び出します。これは 0 です。
return 0 + fib(2-1)
fib()を 1 で呼び出します
return 0 + 1
結果 1 が表示されます。次に、fib(3) を考えます。
n>1 なので
return fib(3-2)+fib(3-1)
3-2 は 1 であるため、最初の項の fib(1) が得られます。これは 1 です。
return 1 + fib(3-1)
そして今、fib(3-1)、つまり fib(2) を呼び出すとき、まだ直接的な答えはありません。n>1。だからそれはなる
return 1 +
return fib(2-2) + fib(2-1)
なる
return 0 + 1
前の呼び出しに戻ります。
return 1 + 1
値 2 を取得します。つまり、独立したスレッドはなく、式全体で機能するだけです。fib(4) の例を作成するための演習として残しておきます。でも、もしそうなら、あなたはそれを釘付けにするでしょう。
簡単なクイズ:反復バージョンの方が劇的に効率的である理由は何ですか?
C＃では、提案どおりにメソッドを簡単に実装できます-次のようになります
public static int Fib(int i) {
if (i == 0) return 0;
if (i == 1) return 1;
return Fib(i - 2) + Fib(i - 1);
}
ただし、ここには魔法はありません。これは、1 回だけの再帰呼び出しとそれに続く別の呼び出しです。つまり、すべてのコードが同じスレッドで順番に実行されます。
各反復で 2 回の再帰呼び出しが行われるため、パフォーマンスも非常に悪くなります。そのため、iこの実装の値が非常に小さい場合でも、役に立たない可能性があります。パフォーマンスが必要な場合は、状態を自分で処理するだけで再帰呼び出しを回避することをお勧めします。
それらは順次評価されます。iefibonacci(1)は is の前に評価されfibonacci(2)ます。視覚化したい場合は、最初の呼び出しツリー (独自の「分割再帰」を使用) を下って、2 番目の 3 つを下る前に戻る場合です。
余談ですが、これは、再帰を使用しない方法の例としてよく使用されます。これは、フィボナッチ数列を評価するのは明らかですが非効率的な方法であるためです。推奨されるオプションは、反復アプローチ (最初の数値を計算し、次に次の数値を計算して目的の数値を計算する) か、さらに優れた方法として、閉じた形式の方程式のいずれかです。