Recursion Tracing...

Question

Lets assume I have a loop for Foo.

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

How many call will occur If i Call Foo(3) and what would be the result...

Thanks

Answer 1

Foo(3) calls Foo(2), Foo(1) and Foo(0)

Foo(1) and Foo(0) return immediately. Now apply the same logic for Foo(2), which doesn't return immediately.

To get the result, draw a tree like this:

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

Continue drawing the tree until you have recursive calls that return immediately (for which the first if returns true), then use those results to calculate the values that are higher in the tree.

You can use the tree to figure out how many recursive calls are made too.

Answer 2

Pass 1: Foo(3)

Pass 2: Foo(2) * Foo(1) * Foo(0)

Pass 3: Foo(1) * Foo(0) * Foo(-1) * 2 * 2

Result: 2 * 2 * 2 * 2 * 2 = 32

Answer 3

Foo(3) would get called 7 times.

Answer 4

How about:

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