Recursion

PropellerAds

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()*/

Try Now – Programming In C MCQs