c
C Programming Tutorial : Introduction

Recursion in C

Recursion is a powerful technique of writing a complicated algorithm in an easy way. According this technique a problem is defined in terms of itself. The problem is solved by dividing it into small problems, which are similar in nature to the original problem. These smaller problems are solved as their solutions are applied to get the final solution of our original problem.

A function that calls itself is known as a recursive function. And this technique is known as recursion.

Syntax-

main()
{
    ... .. ...
    rec();
    ... .. ...
}
void rec()
{
    ... .. ...
    rec();
    ... .. ...
}
 

Here rec( ) is called inside the body of function rec( ). There should be a terminating condition to stop recursion, otherwise, rec( ) will keep on calling itself infinitely and will never return.

Syntax-

rec()
{
…………………………
if ( ... ) /*terrninating condition*/
…………………………
rec ( ) ;
}
 

Before writing a recursive function for a problem we should consider this point-s-

  1. We should be able to define the solution to the problem in terms of a similar type of smaller problem. At each step, we get closer to the final solution to our original problem.
  2. There should be a terminating condition to stop the recursion.

Now we will take some problems and write recursive functions for solving them.

  1. Factorial
  2. Power
  3. Fibonacci numbers,
  4. Tower of Hanoi

Now we’ll write a program, which finds out the factorial using a recursive function.

/*Program to find the factorial of a number by recursive method*/
#include<stdio.h>
#include<conio.h>

long fact (int n);
main ( )
{
int num;
printf("Enter a number ");
scanf("%d",&num);
printf ("Factorial of %d is %ld\n", num, fact (num));
}
long fact (int n)
{
if (n==0)
return(1);
else
return(n*fact(n-1));
}
 

This function returns 1 if the argument n is 0, otherwise it returns n*fact(n-1). To return n*fact(n-1),. The value of fact(n-1) has to be calculated for which fact( ) has to be called again but this time with an argument of n-l. This process of calling fact( ) continues until it is called with an argument of 0.

Suppose we want to find out the factorial of 5.

Initially main( ) calls factorial(5)

Since 5>0, factorial(5) calls factorial(4)

Since 4>0, factorial(4) calls factorial(3)

Since 3>0, factorial(3) calls factorial(2)

Since 2>0, factorial(2) calls factorial(1)

Since 1>0, factorial(1) calls factorial(0)

When factorial( ) is called with n=0 then the condition inside if the statement becomes true, so now the recursion stops and control returns to factorial(1).

Now every called function will return the value to the previous function. These values are returned in the reverse order of function calls.

Recursive functions work in two phases. The first one is the winding phase and the next one is the unwinding phase. In the winding phase, the function keeps on calling itself. The winding phase stops when the terminating condition arrives in a call, now the unwinding phase starts, and the called functions return values in reverse order.

In the above case the function factorial( ) is called 6 times, but there is only one copy of that function in memory. Each function call is different from another because the argument supplied is different each time.

Example-

/*Program to raise a floating point number· to a positive integer sing recursion*/
#include<stdio.h>
float power (float a, int n);
main ( )
{
float a, p;
int n;
printf("Enter a and n ") ;
scanf("%f%d",&a,&n) ;
p=power(a,n) ;
printf("%f raised to power %d is %f\n",a,n,p);
}
float power (float a, int n)
{
if(n==0)
return(l);
else
return(a*power(a,n-1));
}
 
/*Program to generate Fibonacci series using recursion*/
#include<stdio.h>
main ()
{
int nterms, i;
printf ("Enter number of terms ");
scanf ("%d", &nterms);
for(i=0;i<nterms;i++)
printf("%d ",fib(i));
printf("\n");
}
int fib(int n)	/*recursive function that returns nth term of Fibonacci series*/
{
if
(n==0 Iln==1)
return(l);
else
return(fib(n-1)+fib(n-2));
}
 

The difference from the previous two functions (factorial and power) is that here the function fib( ) called two times inside the function body.