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: