Recursion and Stack in C programming

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). You can compare this to the stack of plates in a cafeteria—the last plate that goes on the stack is the first one to get out of it. Now let us see how the stack works in case of the following program.
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 are now popped off.

How the values are being pushed and popped even though we didn’t write any code to do so? Simple—the compiler onencountering the function call would generate code to push parameters and the address. Similarly, it would generate code to clear the stack when the control returns back from fun( ). Figure 5.5 shows the contents of the stack at different stages of execution.

Note that in this program popping of sum and address is done by fun( ), whereas popping of the two integers is done by main( ). When it is done this way it is known as ‘CDecl Calling Convention’. There are other calling conventions as well where instead of main( ), fun( ) itself clears the two integers. The calling convention also decides whether the parameters being passed to the function are pushed on the stack in left-to-right or right-to-left order. The standard calling convention always uses the right-to-leftorder. Thus during the call to fun( ) firstly value of b is pushed to the stack, followed by the value of a.
The recursive calls are no different. Whenever we make a recursive call the parameters and the return address gets pushed on the stack. The stack gets unwound when the control returns from the called function. Thus during every recursive function call we are working with a fresh set of parameters.

Also, note that while writing recursive functions you must have an if statement somewhere in the recursive function to force the function to return without recursive call being executed. If you don’t do this and you call the function, you will fall in an indefinite loop, and the stack will keep on getting filled with parameters and the return address each time there is a call. Soon the stack would become full and you would get a run-time error indicating that the stack has become full. This is a very common error while writing recursive functions. My advice is to use printf( ) statement liberally during the development of recursive function, so that you can watch what is going on and can abort execution if you see that you have made a mistake.