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 ) ;
}
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 is copied into x. Since x turns out to be 1 the condition if ( x == 1 ) is satisfied and hence 1 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
Same way it will work for other values.