4

以下のコードスニペットで再帰呼び出しを理解しようとしています。

static long fib(int n) {
    return n <= 1 ? n : fib(n-1) + fib(n-2);
}

どの関数呼び出しが最初に呼び出されますか？呼び出し後、方程式はどのように機能しますか？

これらの両方が一度呼び出されてから方程式が適用されますか、それとも最初に呼び出されてから2番目のものが呼び出されますか？

たぶん非常に簡単な質問です！

4

5 に答える 5

3

演算子の評価の順序は+定義されていない可能性があります (実装に依存します)。つまり、 fib(n-1)またはfib(n-2)最初に実行される可能性があります。どちらの場合でも、結果は同じになります。この特定のケースでは問題ありません。両方の再帰呼び出しが計算され、返される前に加算されます。呼び出し場所からは、合計の最終結果のみが表示されます。

于 2012-10-16T17:20:26.213 に答える
3

Java と C♯

サブ式は左から右の順序で評価されます。fib(n-1)の前に評価されfib(n-2)ます。Javaでの評価順序の規則は何ですか? を参照してください。

fib()副作用がないため、ここでは評価の順序は重要ではないことに注意してください。

C および C++

2 つの関数は不定の順序で呼び出され、両方が呼び出されると、戻り値が加算されて返されます。左の関数が最初に呼び出されるか、右の関数が最初に呼び出されるかはわかりません。

問題があるように見えるかもしれませんが、そうではありません。なぜなら、それらが呼び出される順序は重要ではないからです。呼び出しfib(i)には副作用 (たとえば、他の変数の変更、メッセージの出力など) がないため、2 つの関数呼び出しは完全に独立しています。

あるコンパイラは、右辺の前に左辺を評価することを決定する場合があります。

 1. f(3)
 2.   f(2)
 3.     f(1)
 4.       return 1
 5.     f(0)
 6.       return 0
 7.     return 1 + 0
 8.   f(1)
 9.     return 1
10.  return 1 + 1

別の例では、左側を評価する前に右側を評価することを決定する場合があります。 

 1. f(3)
 2.   f(1)
 3.     return 1
 4.   f(2)
 5.     f(0)
 6.       return 0
 7.     f(1)
 8.       return 1
 9.     return 1 + 0
10.  return 1 + 1
于 2012-10-16T17:16:06.130 に答える
1

どの関数が最初に呼び出されるかは問題ではありません。この関数は、フィボナッチ数列のn 番目の数を返します。これは、前の 2 つの数を加算することで常に見つけることができます (数列の最初の 2 つが 0 と 1 であるという特殊なケースがあります)。

したがって、この関数が fib(n) を計算するために行うことは、fib(n-1) と fib*(n-2) を要求し、それらを加算して fib(n) を取得することです。もちろん、 fib(n-1) は fib(n-2) と fib(n-3) を要求することで機能し、 fib(n-2) は fib(n-3) と fib(n-4) を要求することで機能します) など、シーケンスの最初 (0 と 1) に到達するまで続きます。これらはそれ以上の再帰なしで返すことができるため、再帰は終了し、開いている各関数はそれを呼び出した関数に戻り、チェーンをずっと遡ります。

これを行うには、2 つの個別の再帰を必要としない、より効率的な方法がありますが、それほどエレガントには見えません。

于 2012-10-16T17:20:04.167 に答える
0

Gcc -S fib.c:

    subl    $1, %eax
    movl    %eax, (%esp)
    call    _fib
    movl    %eax, %ebx
    movl    8(%ebp), %eax
    subl    $2, %eax
    movl    %eax, (%esp)
    call    _fib

したがって、左のものが最初に呼び出されます。じゃあ何？さて、右の枝も同じことを計算していることを知らずに、(n-2) に対しても fib を呼び出します。

このよく知られた例の複雑さは O(n^2) です。つまり、n=10 の場合、10 回で十分ですが、さまざまなパラメーターで自分自身を ~100 回呼び出します。

于 2012-10-16T17:19:54.183 に答える
0

これを理解するために、私は以下のコードを使用し、出力はすべての疑いをクリアしました:(C#)

        static void Main(string[] args)
    {
        var data = series(5);
        Console.WriteLine(data);
    }

    public static int series(int n)
    {
        Console.WriteLine(n);
        if (n ==2)
        {
            return 1;
        }
        if (n == 50)
        {
            return 3;
        }
        else
        {
            return series(2) + series(50);
        }
    }

出力: 5 2 50 4

つまり、左式の再帰を完了してから右に移動します。

于 2019-04-17T16:49:53.703 に答える