C Programming language

Recursion

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.

Example

/*factorial of a number*/
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

Explanation of the program:

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.

Recursion and stack

There are different ways in which data can be organized. For example, if you are to store five numbers then we can store them in five different variables, an array, a linked list, a binary tree, etc. All these different ways of organizing the data are known as data structures. The compiler uses one such data structure called stack for implementing normal as well as recursive function calls. A stack is a Last In First Out (LIFO) data structure. This means that the last item to get stored on the stack (often called Push operation) is the first one to get out of it (often called as Pop operation).

Example

main( )
{
int a = 5, b = 2, c ;
c = add ( a, b ) ;
printf ( "sum = %d", c ) ;
}
add ( int i, int j )
{
int sum ;
sum = i + j ;
return sum ;
}

In this program before transferring the execution control to the function fun( ) the values of parameters a and b are pushed onto the stack. Following this the address of the statement printf( ) is pushed on the stack and the control is transferred to fun( ). It is necessary to push this address on the stack. In fun( ) the values of a and b that were pushed on the stack are referred as i and j. In fun( ) the local variable sum gets pushed on the stack. When value of sum is returned sum is popped up from the stack. Next the address of the statement where the control should be returned is popped up from the stack. Using this address the control returns to the printf( ) statement in main( ). Before execution of printf( ) begins the two integers that were earlier pushed on the stack arenow popped off.