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\n",i);
}
int fact(int n)
{
if(n<=0) \\ B return(1); \\ C else return(n*fact(n-1)); \\ D } Explanation 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 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.

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.