6.26 Recursion

6.26 Recursion

Some problems, (not many,) lend themselves to a recursive solution. Expression evaluation is a good example of a good application of recursion.

You may want to look at Hanly & Koffman Chapter 10 Recursion on page 501..

The following program is recursive implementation of the Fibonacci series, (1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...). In the series (except for the first two numbers) each number is the sum of the previous two.

The program source is available at:
ftp://lt.tucson.az.us/pub/c/recursion.c

/* Louis Taber   PCC  April 8, 2001
 *
 * Recursion example                          */

int fib(int d)  /* Fibonacci series           */
{               /* First two numbers are 1    */
if( d <= 2 ) return 1;
                /* The rest are the sum of    */
                /* the previous two in series */  
else return fib(d-1) + fib(d-2);
}

main()          /* Call Fibonacci series      */
{               /* function fib with values   */
int i;          /* from 1 to 12               */
for( i=1; i<13; i++)
   printf("fib(%2i)=%3d   %c", 
                 i, fib(i), i%3 ? ' ' : '\n' );
return 0;
}

And the output:

fib( 1)=  1    fib( 2)=  1    fib( 3)=  2   
fib( 4)=  3    fib( 5)=  5    fib( 6)=  8   
fib( 7)= 13    fib( 8)= 21    fib( 9)= 34   
fib(10)= 55    fib(11)= 89    fib(12)=144   

6.26 Recursion