Recursion is a process in which a problem is defined in terms of itself. In ‘C’ it is possible to call a function from itself. Functions that call themselves are known as recursive functions, i.e. a statement within the body of a function calls the same function. Recursion is often termed as ‘Circular Definition’. Thus recursion is the process of defining something in terms of itself. To implement recursion technique in programming, a function should be capable of calling itself.
void main()
{
int a;
printf(“Enter a number”);
scanf(“%d”,&a);
fun2(a);
}
int fun2(int b)
{
printf(“%d”,b);
b--;
if(b>=1) /* Termination condition i.e. b is less than 1*/
{
fun2(b);
}
}
How to write a Recursive Function?
Before writing a recursive function for a problem its necessary to define the solution of the problem in terms of a similar type of a smaller problem.
Two main steps in writing recursive function are as follows:
(i). Identify the Non-Recursive part(base case) of the problem and its solution(Part of the problem whose solution can be achieved without recursion).
(ii). Identify the Recursive part(general case) of the problem(Part of the problem where recursive call will be made).
Identification of Non-Recursive part of the problem is mandatory because without it the function
will keep on calling itself resulting in infinite recursion.
How control flows in successive recursive calls?
Flow of control in successive recursive calls can be demonstrated in following example:
Consider the following program which uses recursive function to compute the factorial of a
number.
void main()
{
int n,f;
printf(“Enter a number”);
scanf(“%d”,&n);
f=fact(a);
printf(“Factorial of %d is %d”,n,f);
}
int fact(int m)
{
int a;
if (m==1)
return (1);
else
a=m*fact(m-1);
return (a);
}
In the above program if the value entered by the user is 1 i.e.n=1, then the value of n is copied into m. Since the value of m is 1 the condition ‘if(m==1)’ is satisfied and hence 1 is returned through return statement i.e. factorial of 1 is 1.
When the number entered is 2 i.e. n=2, the value of n is copied into m. Then in function fact(), the condition ‘if(m==1)’ fails so we encounter the statement a=m*fact(m-1); and here we meet recursion. Since the value of m is 2 the expression (m*fact(m-1)) is evaluated to (2*fact(1)) and the result is stored in a(factorial of a). Since value returned by fact(1) is 1 so the above expression reduced to (2*1) or simply 2. Thus the expression m*fact(m-1) is evaluated to 2 and stored in a and returned to main(). Where it will print ‘Factorial of 2 is 2’.
In the above program if n=4 then main() will call fact(4) and fact(4) will send back the computed value i.e. f to main(). But before sending back to main() fact(4) will call fact(4-1) i.e. fact(3) and wait for a value to be returned by fact(3). Similarly fact(3) will call fact(2) and so on. This series of calls continues until m becomes 1 and fact(1) is called, which returns a value which is so called as termination condition. So we can now say what happened for n=4 is as follows
fact(4) returns (4*fact(3) ) fact(3) returns (3*fact(2) ) fact(2) returns (2*fact(1) ) fact(1) returns (1)
Winding and Unwinding phase
All recursive functions work in two phases- winding phase and unwinding phase.
Winding phase starts when the recursive function is called for the first time, and ends when the termination condition becomes true in a call i.e. no more recursive call is required. In this phase a function calls itself and no return statements are executed. After winding phase unwinding phase starts and all the recursive function calls start returning in reverse order till the first instance of function returns. In this phase the control returns through
each instance of the function.
Implementation of Recursion
We came to know that recursive calls execute like normal function calls, so there is no extra technique to implement recursion. All function calls(Whether Recursive or Non-Recursive) are implemented through run time stack. Stack is a Last In First Out(LIFO) data structure. This means that the last item to be stored on the stack(PUSH Operation) is the first one which will be deleted(POP Operation) from the stack. Stack stores Activation Record(AR) of function during run time. Here we will take the example of function fact() in the previous recursive program to find factorial of a number.
Suppose fact() is called from main() with argument 3 i.e.
fact(3); /*From main()*/
