递归跟踪

Question

让我们假设我有一个Foo循环.

int Foo(int n)
{
   if (n <= 1)
      return 2;
   else
      return Foo(n-1) * Foo(n-2) * Foo (n-3);
}

如果我打电话给Foo(3)会有多少电话会发生...

谢谢

Answer 1

Foo(3)电话Foo(2),Foo(1)和Foo(0)

Foo(1)并Foo(0)立即返回.现在应用相同的逻辑Foo(2),但不会立即返回.

要获得结果,请绘制如下树:

            Foo(3)
      /       |        \
   Foo(2)   Foo(1)   Foo(0)

继续绘制树,直到您有立即返回的递归调用(第一个if返回true),然后使用这些结果计算树中较高的值.

您可以使用树来确定也进行了多少次递归调用.