Recursion

One concept that many C programmers find difficult to digest is that of Recursion. It's a substitute for iteration which is implemented in C using while, for or do-while. Let us examine this concept in detail. A function is called recursive if a statement within the body of a function calls the same function. Sometimes called circular definition, recursion is thus the process of defining something in terms of itself. Taking the example of calculating the factorial value of a number, let us see the working of a recursive function.

main( )

{

int a, fact ;

printf ( "Enter any number " ) ;

scanf ( "%d", &a ) ;

fact = rec ( a ) ;

printf ( "Factorial value = %d", fact ) ;

}

rec ( int x )

{

int f ;

if ( x == 0 )

return ( 1 ) ;

else

f = x * rec ( x - 1 ) ;

return ( f ) ;

}

Assume that the number entered is 3. Using the figure given below, we try to visualise what exactly happens when the recursive function rec( ) gets called.

Go through the figure carefully. The first time when rec( ) is called from main( ), x collects 3. From here, since x is not equal to 1, the if block is skipped and rec( ) is called again with argument ( x - 1 ), i.e. 2. This is a recursive call. Since x is still not equal to 1, rec( ) is called yet another time, with argument ( 2 - 1 ). This time as x is 1, control goes back to the previous rec( ) with the value 1, and f is evaluated as 2. Similarly, each rec( ) evaluates its f from the returned value, and finally 6 is returned to main( ). The sequence would be grasped better by following the arrows in the figure. Let it be clear that while executing the program there do not exist so many copies of the function rec( ). These have been shown in the figure just to help you keep track of how the control flows during successive recursive calls.

Recursion may seem strange and complicated at first glance, but it is often the most direct way to code an algorithm - and, once you get the hang of recursion, the most direct way of doing so.