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).