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

你必须记住，递归基本上是构建一个函数调用的“树”——它会尽可能地沿着树向下走，然后上一层，看看它还需要做什么才能继续。我不确定这有多清楚，但希望它有所帮助。

Answer 2

它真的很简单（一旦你把头绕在它周围）。在最后一行中，您调用了函数 foo 两次并将它们的返回值相加。

这是一个示例跟踪

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()的另外两次调用。这两个中的每一个依次调用自己的两个，依此类推。

第一次迭代

富（）

第二次迭代

富（）富（）

第三次迭代

富() 富() 富() 富()

等等

因此，如果 foo() 没有达到终止条件之一，它总是会再调用自己两次。

添加一个指示调用深度的变量并让 foo() 打印出它的参数（包括调用深度参数）可能是有益的。