Recursion in C

Recursion in C

Recursion in C

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,

1st   term = 0

2nd term = 1

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

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

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

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

7th term=5th term + 6th 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.

Similar Posts:

You may also Like :

To Download Official TurboC Compiler from here

Hope recursion is clear to you . If you have any doubt please comment so that I can answer it accordingly.

 

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.
0 0 votes
Article Rating
Subscribe
Notify of
guest
5 Comments
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
trackback
11 months ago

[…] Recursion in C                        Bit Fields in C Language                          Structures in C […]

trackback
10 months ago

[…] Topics :         Recursion in C            Preprocessor Directives in C                    File, Stream and […]

trackback
10 months ago

[…] Recursion in C […]

trackback
10 months ago

[…] Recursion in C […]

trackback
9 months ago

[…] of Accounts in Tally Prime           Recursion in C             Let us Learn JavaScript from Step By […]

Please Subscribe to Stay Connected

You have successfully subscribed to the newsletter

There was an error while trying to send your request. Please try again.

DigitalSanjiv will use the information you provide on this form to be in touch with you and to provide updates and marketing.
Share via
Copy link
Powered by Social Snap
%d bloggers like this: