Recursive Functions

1. Introduction

 

We know that a function is a unit of code that performs a specific task needed by the application in many places. Also we know that depending on the need it may take some parameters and do some task based on the input provided in the form of parameters and returns the value to the caller. There is other code that calls a function, passes the required parameters, does the job and returns the values.

 

We call a function a recursive function when the function makes a call to itself. Here the caller and called function is same.  In this article, we will look at how do we use recursive functions and what the behavior of the variables in a function call stack scope is.

 

2. Function Call Stack

 

All the variables that you declare inside the function without static keywords are known as Auto Variables. These variables will come alive when the function starts and dies when it returns to the caller. When it is called again, once again the auto variable comes alive. If you see, between the function calls the variable losses its value and that why we do animalize the variables with some values before we start using it inside the function.

 

In case of recursive functions the same concepts hold true. When there are two different functions acts as caller and called functions, you may not get any confusion saying Called function can not see the variable of the Calling function.

 

3. The example

 

The function in the below example takes a number as the parameter and prints number in forward and reverse order. The code is given below:

 

#include "stdafx.h"

#include <conio.h>

 

 

void PrintSeries(int NumTimes)

{

            int LocalNo;

            static int x = 0;

 

            //Return to the caller when NumTimes is 0. >100 is to avoid Stack overflow.

            if (NumTimes == 0 || NumTimes > 100)

                        return;

 

            //Print the value in x and store that in Local Variable LocalNo.

            x++;

            printf("%d ", x);

            LocalNo = x;

 

            //Make a recursive call giving a parameter by reducing it value by 1. Helpful to make a exit based on NumTimes == 0

            NumTimes = NumTimes - 1;

            PrintSeries(NumTimes);

 

            //See the Magic. It makes you to understand what is Function stack

            printf("%d ", LocalNo);

 

            //The value in the Static variable at the bottom of the call statck

            if (LocalNo == 1 )

                        printf("Static variable value: %d ", x);

}

 

 

int _tmain(int argc, _TCHAR* argv[])

{

            //Make call to PrintSeries.

            PrintSeries(12);

 

            getch();

            return 0;

}

 

Output:

 

4. Explanation

 

1. The function takes an integer as parameter and if you pass 3 it should print 1 2 3 3 2 1. 

The Function signature is given below

 

void PrintSeries(int NumTimes)

 

2. It has two variables declared inside. The code is given below:

            int LocalNo;

            static int x = 0;

 

LocalNo is the auto variable and gets created in the stack of the function when it called and losses its value when it returns. Also note that the visibility is inside the functions only. That is function other than PrintSeries(int) can not able to access it. The variable x is static and like auto variable LocalNo it can be accessed only by the PrintSeries function. We call this as variable visibility. The variable x will not lose value when function return and it will die only when the executable program ends. We call this life time as variable scope. So I can say, Scope and visibilty of the LocalNo is inside PrintSeries or Stack of the print series. At the same time visibility of x is inside the function printseries, but the scope is through out the program. That means it will not lose its value.

 

3. In the case of recursive function we should make sure that the function should come out of the recursive chain in any case. If you fail to do it, then it causes damage to the execution as stack frame currupts and the instruction pointer do not where should it go when the function actually returns. Below is the return statement in our example:

 

            //Return to the caller when NumTimes is 0. >100 is to avoid Stack overflow.

            if (NumTimes == 0 || NumTimes > 100)

                        return;

 

We return from the function when the passed in number is more than 100 just to be on safer side for not making too much recursive chain in the call stack. The more imprtant one is we return when the Paremeter Numtimes = 0. When I make a recursive call, I will make sure to reduce the parameter value by 1 so that return will actually happen and recrsion chain will ends.

 

4. Before making a recursive call, I increment the static variable by 1 and print it. This will produce the incremting numbers in the output goes deep inside the recursive chain untill it touches the return by satisfying the condition Numtimes == 0. Also I am decremeting the parameter value by one and passing that value when I make a recursive call.

 

            //Print the value in x and store that in Local Variable LocalNo.

            x++;

            printf("%d ", x);

            LocalNo = x;

 

            //Make a recursive call giving a parameter by reducing it value by 1. Helpful to make a exit based on NumTimes == 0

            NumTimes = NumTimes - 1;

            PrintSeries(NumTimes);

 

Note that I am storing the Static variable value inside the local variable LocalNo using LocalNo = x before making a recursive call. It is useful for you know how Static and Auto variable behave between the recursion. It makes you to understand, variable LocalNo live in the function Stack portion of memory and variable x lives program data portion of the memory.

 

Ok. Now how the recursion happens. See we made a call to the same function. What happens now? The caller should wait for the called function (The same function which has a different call stack and whos stack frame is one above the caller) to return. Now, the called function may return and may not based on the condition    if (NumTimes == 0 || NumTimes > 100). If you passed a number between 1 through 99 it will not return. What happens if it does not return? The called function makes a call to itself and there by adding one more call stack in the recursion chain. OK. I think, I am confusing you, if you are beginner. Keep reading, you will have a better undertanding once you finsihed reading it and do a debug & watch.

 

5. When you write recursive functions, keep in mind three things that will help you code it better. a) Think about the way you should return from the recursion. b) Piece of code before the recursive call. C) Piece  of code after the recursive call. We saw the improtance of return to ends the recursion chain already in the previous point. The code you write before the recursive call get executed till recursion stops growing. When the recursion started shrinking, the code next to the call gets executed.

 

            //See the Magic. It makes you to understand what is Function stack

            printf("%d ", LocalNo);

 

            //The value in the Static variable at the bottom of the call statck

            if (LocalNo == 1 )

                        printf("Static variable value: %d ", x);

 

The recursion and its ending of the example is shown below:

 

 

The stack variable and auto variable usage is shown below and please note that black separator is the statement that makes the recursive call: