Recursion in C

Table of Contents

Recursion

A function can call itself directly or indirectly is called recursion, and the function that calls itself (directly or indirectly) is known as recursive function. In C Language, any function can call itself, including main( ) function.

Example

       main( )
       {
               printf(“Ha Ha Ha…!  I cannot stop this.”);
               main( ) ;
       }

The above program will result in continuous printing “Ha Ha Ha . . . ! I cannot stop this.” and does not stop until CTRL+BREAK is pressed. This happens because a recursive function definition is not complete without an outgoing condition, which is called a base criteria.

The base case/condition terminates the recursive function. So, for a recursive function to not continue indefinitely, it must have following two properties .

There must be base condition(s) for which the function does not call itself, to terminate the recursive function.
Each time the recursive function calls itself (directly or indirectly), the function must try to get closer to the base condition(s). For the functions having arguments, the arguments should try to get closer to satisfy base condition(s).

A recursive function is considered well-defined only if it has above two properties.

Now the above program, can be modified to make a perfect recursive function

            main( )
            {
              static int count=0 ;
              printf(“Ha Ha Ha . . . !   I cannot stop this. “) ;
              count++ ;
              if(count==5)  ;       /* terminating condition */
              main( ) ;
        }

Recursive functions are useful in evaluating certain types of mathematical functions. You may also encounter certain dynamic data structures such as linked lists or binary trees. Recursion is a very useful way of creating and accessing these structures. Programs involving artificial intelligence techniques including games are also coded easily using recursion.

Simple example of a recursive function for adding first n natural numbers !

#include<stdio.h>
int sum(int n)
{
       if (n==1)                                         /* base condition*/
              return n;
        else
              return n=n+sum(n-1); 
}
void main( )
{
     int n;
    printf(“Enter the limit upto which you want sum of natural numbers : “);
   scanf(“%d”,&n);
   printf(“sum of first %d natural numbers  = %d”,n,sum(n));
}

in the above, be program if n=5, then sum (n) will called recursively as shown below :

sum(5)=5+sum(4)

sum(4) = 4+sum(3)

sum(3) =3+sum(2)

sum(2) =2+sum (1)

sum(1) =1 (base condition [if (n==1) return n ;] fulfils)

sum(2) =2+1=3

sum(3) =3+3=6

sum(4)=4+6=10

sum(5)=5+10=15

Write a function to find the factorial of a number recursive.

It is known to us that factorial of 0 is 1 (i.e., 0!=1), and that factorial of any number n>0 is found as;

n ! = n* (n-1) * (n-2) * . . . *3*2*1

so, we can write this definition recursively as

n! = { n* (n-1)!}, if n>0

now, we can easily write a function to find factorial of a number as:

long factorial (int n)
       {
              if (n<0) return 0;          /* illegal value*/
              if (n==0) return 1;        /* 0! = 1  */
              else
              return n*factorial(n-1);  /* n! = n* (n-1)  !   */
       }

Second options

long factorial (int n)
{
   if (n<0) return 0;
   return((n==0)?1:n*factorial(n-1);
}

Example

#include<stdio.h>
long factorial (int n)
{
if(n<0) return 0;         /* illegal value*/
if(n==0) return 1;             /* 0! = 1  */
else
return n*factorial(n-1);      /* n! = n* (n-1)  !   */
}
void main( )
{
int n;
printf(“Enter the value up to which you want factorial of natural numbers : “);
scanf(“%d”,&n);
printf(“Factorial of %d natural numbers  = %d”,n,factorial(n));
}

Write a function to find the Fibonacci series: 0 1 1 2 3 5 8 13 21 34 55 . . . up to n terms.

In the Fibonacci series, the noticeable thing is that is starts with the first two terms 0 and 1, and then next terms are obtained by adding the previous two terms.

For example,

1^st term = 0

2^nd term = 1

3^rd term= 1^st term + 2^nd term =0+1 = 1

4^th term=2^nd term + 3^rd term = 1+1 =2

5^th term = 3^rd term + 4^th term = 1+2 =3

6^th term=4^th term + 5^th term = 2+3 =5

7^th term=5^th term + 6^th term = 3+5=8

and so on . . .

So, we can write the recursive definition of finding the (n+1)th term (n=0 ,1,2,3,. . . .) of Fibonacci series as :

fibo(n) ={fibo(n-2) + fibo(n-1)} , if n>1

Now, we can easily write a recursive function to find (n+1)th term (n=0,1,2,3, . . . ) of Fibonacci series using two different algorithms:

long fibo(int n)
{
if (n==0 | | n==1)
return n;
else
return (fibo(n-2)  + fibo(n-1));
}

long fibo(int n)
{
return ((n==0||n==1)?n:(fibo(n-2)+fibo(n-1)));
}

Let us write a program to find the (n+1)^th term of a Fibonacci Series-

#include<stdio.h>
long fibo(int n)
{
if (n==0 | | n==1)
return n;
else
return (fibo(n-2) + fibo(n-1));
}
void main()
{
int n;
printf(“Enter term up to which you want fibonacci series : “);
scanf(“%d”,&n);
printf(“Fibonacci Series of %d terms is  = %d”,n+1,fibo(n));
}

Recursive Quick Sort

Quick sort is used to sort the elements of an array. To carryout sorting process partitioning method is used.

Partitioning

partitioning means arranging the elements less than the pivot to its left and greater ones to the right.

Pivot

Pivot is the key element of the array which can be chosen arbitrarily from its elements.

To sort an array of n elements, following sequence is followed-

1) Initially let low=0, high=n

2) Select the pivot element to partition numbers. Let pivot leaves a space in the location (i.e low) it was stored.

3) Now start reading elements from the right and find an element smaller than the key element . Set the location where the smaller elements found to high. Fit this element in the location low . This leaves a space in the location high.

4) Next read elements from the left this time starting from the location low to fund an element larger than pivot. Set the location where this larger element is found to low. Fit this element in the location high. leaving space in the location low.

5) When low=high stop. No further moves are possible and position for locating the pivot has been attained. Put the pivot in the location low or high.

What is Recursion

When a function calls itself directly or indirectly is called recursion. Recursion is really helpful in solving repetitive mathematical problems. Recursion is heavily used in Artificial Intelligence.