6.27 Function pointers6 Notes6.25 Conversion Functions6.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   

Instructor: Louis Taber, louis.taber.at.pima at gmail dot com (520) 206-6850
My web site in Cleveland, OH
The Pima Community College web site

6.27 Function pointers6 Notes6.25 Conversion Functions6.26 Recursion