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

.
- The parameter
`n=3`

. - We test to see if
`n=0`

. - Since it doesn't we need to compute
`n*fact(n-1)`

so we call`fact()`

.- The parameter
`n=2`

. - We test to see if
`n=0`

. - Since it doesn't we need to compute
`n*fact(n-1)`

so we call`fact()`

.- The parameter
`n=1`

. - We test to see if
`n=0`

. - Since it doesn't we need to compute
`n*fact(n-1)`

so we call`fact()`

.- The parameter
`n=0`

. - We test to see if
`n=0`

. - Since it does we return 1 as the result of
`fact(0)`

.

- The parameter
- With
`fact(0)=1`

we compute`n*fact(n-1)`

for`n=1`

. - This returns 1 as the result of
`fact(1)`

.

- The parameter
- With
`fact(1)=1`

we compute`n*fact(n-1)`

for`n=2`

. - This returns 2 as the result of
`fact(2)`

.

- The parameter
- With
`fact(2)=2`

we compute`n*fact(n-1)`

for`n=3`

. - 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:
- G(0)=1
- G(n)=2*G(n-1) for all n > 0

`g`

(lower case).