Mastering Recursion in C: Tips and Tricks

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.