Recursion

Ads by YahooAds.in

Recursion in C

In C, it is possible for the functions to call themselves. 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.

Let us now see a simple example of recursion. Suppose we want to calculate the factorial value of an integer.
As we know, the factorial of a number is the product of all the integers between 1 and that number.

For example, 4 factorial is 4 * 3 * 2 * 1. This can also be expressed as 4! = 4 * 3! where ‘!’ stands for factorial.
Thus factorial of a number can be expressed in the form of itself.
Hence this can be programmed using recursion.

Following is the recursive version of the function to calculate the
factorial value.

main( )
{
int a, fact ;
printf ( "\nEnter any number " ) ;
scanf ( "%d", &a ) ;
fact = rec ( a ) ;
printf ( "Factorial value = %d", fact ) ;
}
rec ( int x )
{
int f ;
if ( x == 1 )
return ( 1 ) ;
else
f = x * rec ( x - 1 ) ;
return ( f ) ;
}

And here is the output for four runs of the program

Enter any number 1
Factorial value = 1
Enter any number 2
Factorial value = 2
Enter any number 3
Factorial value = 6
Enter any number 5
Factorial value = 120


Description :

Let us understand this recursive factorial function thoroughly. In the first run when the number entered through scanf( ) is 1, let us see what action does rec( ) take. The value of a (i.e. 1) is copied into x.

Since x turns out to be 1 the condition if ( x == 1 ) is satisfied and hence 1 (which indeed is the value of 1 factorial) is returned through the return statement.

When the number entered through scanf( ) is 2, the ( x == 1 ) test fails, so we reach the statement,
f = x * rec ( x - 1 ) ;

And here is where we meet recursion. How do we handle the expression x * rec ( x - 1 )?
We multiply x by rec ( x - 1 ). Since the current value of x is 2, it is same as saying that
we must calculate the value (2 * rec ( 1 )).
We know that the value returned by rec ( 1 ) is 1, so the expression reduces to (2 * 1), or simply 2.

Thus the statement,
x * rec ( x - 1 ) ;

evaluates to 2, which is stored in the variable f, and is returned to main( ), where it is duly printed as Factorial value = 2

Now perhaps you can see what would happen if the value of a is 3, 4, 5 and so on.

In case the value of a is 5, main( ) would call rec( ) with 5 as its actual argument, and rec( ) will send back the computed value.
But before sending the computed value, rec( ) calls rec( ) and waits for a value to be returned.
It is possible for the rec( ) that has just been called to call yet another rec( ), the argument x being decreased in value by 1 for each of these recursive calls.

So we might say what happens is,

rec ( 5 ) returns ( 5 times rec ( 4 ),
which returns ( 4 times rec ( 3 ),
which returns ( 3 times rec ( 2 ),
which returns ( 2 times rec ( 1 ),
which returns ( 1 ) ) ) ) )

     Prev                                                   NEXT

Ads by YahooAds.in