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