recursion - この単純な再帰コードを理解しようとしています

Question

この単純な再帰を理解するのを手伝ってください。私はプログラミングに非常に慣れていないので、これがどのように段階的に起こるのか疑問に思っています。

再帰を学ぼうとしていますが、「+」の追加で行き詰まっています

function foo($bar) {
  if ($bar == 1) return 1;
  elseif ($bar == 0) return 0;
  else return foo($bar - 1) + foo($bar - 2);
}

Answer 1

再帰を理解しようとするとき、特定のパラメーターの個々のケースを書き留めて、そこから理解を深めることが非常に役立つことがわかりました。

それでは、次の例を見てみましょうfoo(3)

foo(3) -> どちらの基本ケースにも該当しないため、関数は戻りたいと考えています。

foo(2) + foo(1)

まず foo(2) を取得する必要があります

foo(2) -> 再び基本ケースがないため、戻ります

foo(1) + foo(0)

foo(1) = 1 および foo(0) = 0 (これらは基本的なケースです) なので、

foo(2) = 1 + 0

これで、foo(3) を見ると次のように解決されます。

foo(3) -> (1 + 0) + foo(1)

foo(1) = 1 なので、最終的に

foo(3) -> (1 + 0) + 1 = 2

再帰は基本的に関数呼び出しの「ツリー」を構築していることを覚えておく必要があります。これは、ツリーを可能な限り下に移動し、次に 1 レベル上に移動して、続行するために他に何をする必要があるかを確認します。これがどれほど明確かはわかりませんが、うまくいけば役に立ちます。

Answer 2

それは本当に簡単です（頭を包むと）。最後の行では、関数 foo を 2 回呼び出して、それらの戻り値を一緒に追加しています。

ここにサンプルトレースがあります

call 1:
    foo(3)
    return foo(2) + foo(1)

    call 2:
        foo(2)
        return foo(1) + foo(0)

        call 3:
            foo(1)
            return 1

    unrolls to call 2:
        return 1 + foo(0)

        call 4:
            foo(0)
            return 0

    unrolls to call 2 again:
        return 1 + 0

unrolls to call 1:
    return 1 + foo(1)

    call 5:
        foo(1)
        return 1

unrolls to call 1 again:
    return 1 + 1

Answer 3

foo()の最初の呼び出しは、foo()の追加の 2 つの呼び出しを呼び出すことになります。これらの 2 つのそれぞれが、自分自身の 2 つを順番に呼び出します。

最初の繰り返し

フー()

2 回目の繰り返し

フー() フー()

3回目の繰り返し

foo() foo() foo() foo()

等

したがって、foo() がいずれかの終了条件を満たさない場合は、常に自分自身をさらに 2 回呼び出します。

呼び出しの深さを示す変数を追加し、呼び出しの深さの引数を含む引数を foo() に出力させることは有益かもしれません。