Recursion

Introduction

You can express most of the problems in the following program by using recursion. We represent the function add by using recursion.

Program

#include 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 ",i); } int add(int pk,int pm) { if(pm==0) return(pk); \ A else return(1+add(pk,pm-1)); \ B }

Explanation

1. 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

2. The recursive expression is 1+add(pk, pm-1). The terminating condition is pm = 0 and the recursive condition is pm > 0.

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 ",i); diff = old-current; printf("stack overheads are %16lu ",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 ",&j,&m); \D if(n<=0) return(1); else return(n*fact(n-1)); }

Explanation

1. The program calculates factorials just as the previous program.
2. The variable to be analyzed is the local variable j, which is the automatic variable. It gets its location in the stack.
3. 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.
4. 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.
5. 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.
6. In the next call, m is 1 and the value of j is stored in current.
7. Note that the addresses of j are stored in long variables of type castings.
8. old and current store the address of j in consecutive calls, and the difference between them gives the stack overheads.
9. You can also check the address of j and check how the allocation is done in the stack and how the stack grows.

Points to Remember

1. The recursive program has a stack overhead.
2. You can calculate stack overheads by analyzing the addresses of local variables.

WRITING A RECURSIVE FUNCTION

Introduction

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 int fact(int n); main() { int k = 4,i; i =fact(k); \ A printf("The value of i is %d ",i); } int fact(int n) { if(n<=0) \ B return(1); \ C else return(n*fact(n-1)); \ D }

Explanation

1. You can express factorials by using recursion as shown:

   fact (5) = 5 * fact (4) In general, fact (N) = N * fact (N-1) fact 5 is calculated as follows: fact (5) = 5 * fact (4) i.e. there is call to fact (4) \ A fact (4) = 4 * fact (3) fact (3) = 3 * fact (2) fact (2) = 2 * fact (1) fact (1) = 1 * fact (0) fact (0) = 1 \ B fact (1) = 1 * 1, that is the value of the fact(0) is substituted in 1. fact (2) = 2 * 1 = 2 fact (3) = 3 * 2 = 6 fact (4) = 4 * 6 = 24 fact (5) = 5 * 24 = 120 \ C

2. 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,

   fact ( N) = N * fact (N-1) N > 0 = 1 N = 0

   • N * fact (N-1) indicates a recursive expression.
   • N > 0 indicates a recursive condition.
   • N = 0 indicates a terminating condition.

3. 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.
4. 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

1. Recursion enables us to write a program in a natural way. The speed of a recursive program is slower because of stack overheads.
2. In a recursive program you have to specify recursive conditions, terminating conditions, and recursive expressions.