You can express most of the problems in the
following program by using recursion. We represent the function add by using recursion.
Program
#include <stdio.h>
int add(int pk,int pm);
main()
{
int k
,i,m;
m=2;
k=3;
i=add(k,m);.
printf("The value of addition is %d\n",i);
}
int add(int pk,int pm)
{
if(pm==0)
return(pk); \\ A
else
return(1+add(pk,pm-1)); \\ B
}
Explanation
- The add function is recursive as
follows:
- add (x, y) = 1 + add(x,
y-1) y > 0
- = x y = 0
- for example,
- add(3, 2) = 1 + add(3, 4)
- add(3, 1) = 1 + add(3, 0)
- add(3, 0) = 3
- add(3, 1) = 1+3 = 4
- add(3, 2) = 1+4 = 5
- The recursive expression is 1+add(pk, pm-1). The terminating condition
is pm =
0 and
the recursive condition is pm > 0.
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 <stdio.h>
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);
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
|
Points to Remember
- The recursive program has a
stack overhead.
- You can calculate stack
overheads by analysing the addresses of local variables.
A
recursive function is a function that calls itself. Some problems can be easily
solved by using recursion, such as when you are dividing a problem into sub-
problems with similar natures. Note that recursion is a time-consuming solution
that decreases the speed of execution because of stack overheads. In recursion,
there is a function call and the number of such calls is large. In each call,
data is pushed into the stack and when the call is over, the data is popped
from the stack. These push and pop operations are time-consuming operations. If
you have the choice of iteration or recursion, it is better to choose iteration
because it does not involve stack overheads. You can use recursion only for
programming convenience. A sample recursive program for calculating factorials
follows.
Program
#include <stdio.h>
int fact(int n);
main()
{
int k =
4,i;
i
=fact(k); \\ A
printf("The value of i is %d\n",i);
}
int fact(int n)
{
return(1); \\ C
else
return(n*fact(n-1)); \\ D
}
Explanation
- You can express factorials
by using recursion as shown:
2. fact (5) = 5 * fact (4)
3. In general,
4. fact (N) = N * fact (N-1)
5. fact 5 is calculated as follows:
6. fact (5) = 5 * fact (4) i.e. there is call to fact
(4) \\ A
7. fact (4)
= 4 * fact (3)
8. fact (3)
= 3 * fact (2)
9. fact (2)
= 2 * fact (1)
10. fact (1)
= 1 * fact (0)
11. fact (0)
= 1 \\ B
12.fact (1) = 1 * 1, that is the value of the fact(0)
is substituted in 1.
13. fact (2)
= 2 * 1 = 2
14. fact (3)
= 3 * 2 = 6
15. fact (4)
= 4 * 6 = 24
16. fact (5)
= 5 * 24 = 120 \\ C
- The operations from
statements B to A are collectivelly called the winding phase, while
the operations from B to C are called the unwinding phase. The winding
phase should be the terminating point at some time because there is no
call to function that is given by statement B; the value of the argument
that equals 0 is the terminating condition. After the winding phase is
over, the unwinding phase starts and finally the unwinding phase ends at
statement C. In recursion, three entities are important: recursive
expressions, recursive condition, and terminating condition. For example,
18.fact ( N) = N * fact (N-1) N > 0
19. = 1
N = 0
- N * fact (N-1) indicates a recursive
expression.
- N > 0 indicates a recursive
condition.
- N = 0 indicates a terminating
condition.
- You should note that the
recursive expression is such that you will get a terminating condition
after some time. Otherwise, the program enters into an infinite recursion and you will get a stack overflow
error. Statement B indicates the terminating condition, that is, N = 0.
- The condition N > 0 indicates a recursive
condition that is specified by the else statement. The recursive expression is n * fact(n-1), as given by statement D.
Points to Remember
- Recursion enables us to
write a program in a natural way. The speed of a recursive program is
slower because of stack overheads.
- In a recursive program you
have to specify recursive conditions, terminating conditions, and
recursive expressions.