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, thefactorial 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. However, before we try to write a recursive function for calculating factorial let us take a look at the non-recursive function for calculating the factorial value of an integer.
main( )
{
int a, fact ;
printf ( "\nEnter any number " ) ;
scanf ( "%d", &a ) ;
fact = factorial ( a ) ;
printf ( "Factorial value = %d", fact ) ;
}
factorial ( int x )
{
int f = 1, i ;
for ( i = x ; i >= 1 ; i-- )
f = f * i ;
return ( f ) ;
}
And here is the output...
Enter any number 3
Factorial value = 6
Work through the above program carefully, till you understand the logic of the program properly. Recursive factorial function can be understood only if you are thorough with the above logic.
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
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 beenFactorial value = 6
Enter any number 5
Factorial value = 120
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 beenhelp 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 are familiar with recursion, the clearest way of doing so.
