How Can You Call Yourself?

The answer is "very carefully." Let us begin by implementing the factorial function in C. 
int fact(int n)
{
   if(n == 0)
      return 1;
   else
      return n * fact(n - 1);
}
Let's trace the flow for a call of fact(3) .
  1. The parameter n=3 .
  2. We test to see if n=0 .
  3. Since it doesn't we need to compute n*fact(n-1) so we call fact() .
    1. The parameter n=2 .
    2. We test to see if n=0 .
    3. Since it doesn't we need to compute n*fact(n-1) so we call fact() .
      1. The parameter n=1 .
      2. We test to see if n=0 .
      3. Since it doesn't we need to compute n*fact(n-1) so we call fact() .
        1. The parameter n=0 .
        2. We test to see if n=0 .
        3. Since it does we return 1 as the result of fact(0) .
      4. With fact(0)=1 we compute n*fact(n-1) for n=1 .
      5. This returns 1 as the result of fact(1) .
    4. With fact(1)=1 we compute n*fact(n-1) for n=2 .
    5. This returns 2 as the result of fact(2) .
  4. With fact(2)=2 we compute n*fact(n-1) for n=3 .
  5. This returns 6 as the result of fact(3) .

Next, let's look at a recursive function for Fibonacci numbers. 

int fibb(int n)
{
   if(n == 1 || n == 2)
      return 1;
   else
      return fibb(n - 1) + fibb(n - 2);
}
Notice here that we can have more than one place where a function calls itself. As an exercise, you should trace through a call of fibb(3) .
Consider again the function G() defined by:
  1. G(0)=1
  2. G(n)=2*G(n-1) for all n > 0
Write the return statement that corresponds to part 2 of the definition assuming that the function is named g (lower case).