STACK OVERHEADS IN RECURSION

Introduction
If you analyze the address of local variables of the recursive function, you will get two important results: the depth of recursion and the stack overheads in recursion. Since local variables of the function are pushed into the stack when the function calls another function, by knowing the address of the variable in repetitive recursive call, you will determine how much information is pushed into the stack. For example, the stack could grow from top to bottom, and the local variable j gets the address 100 in the stack in the first column. Suppose stack overheads are 16 bytes; in the next call j will have the address 84, in the call after that it will get the address 16. That is a difference of 16 bytes. The following program uses the same principle: the difference of the address in consecutive calls is the stack overhead.

Program
#include
int fact(int n);
long old=0; \\E
long current=0; \\F
main()
{
int k = 4,i;
long diff;
i =fact(k);
printf("The value of i is %d\n",i);
diff = old-current;
printf("stack overheads are %16lu\n",diff);
}
int fact(int n)
}
int j;
static int m=0;
if(m==0) old =(long) &j; \\A
if(m==1) current =(long) &j; \\B
m++; \\C
printf("the address of j and m is %16lu %16lu\n",&j,&m); \\D
if(n<=0)
return(1);
else
return(n*fact(n-1));
}

Explanation
The program calculates factorials just as the previous program.

The variable to be analyzed is the local variable j, which is the automatic variable. It gets its location in the stack.

The static variable m is used to track the number of recursive calls. Note that the static variables are stored in memory locations known as data segments, and are not stored in stack. Global variables such as old and current are also stored in data segments.

The program usually has a three-segment text: first, storing program instructions or program code, then the data segment for storing global and static variables, and then the stack segment for storing automatic variables.

During the first call, m is 0 and the value of j is assigned to the global varable old. The value of m is incremented.

In the next call, m is 1 and the value of j is stored in current.

Note that the addresses of j are stored in long variables of type castings.

old and current store the address of j in consecutive calls, and the difference between them gives the stack overheads.

You can also check the address of j and check how the allocation is done in the stack and how the stack grows.

Note You can also check whether the address of m is constant.


Points to Remember
The recursive program has a stack overhead.

You can calculate stack overheads by analyzing the addresses of local variables.