recursion in c language

Recursion in c language

Social Shares
  • 1
  •  
  •  
  • 1
  •  
  •  
  •  
  •  

Introduction to C Recursion 

Recursion in C language is a process in which a function calls itself. This is done to solve a problem by dividing it into smaller parts. Functions that call themselves are called recursive functions.

Suppose you are creating a function to solve a problem and its initial result is not the end result. To get the end result you need to repeat this process back.

In such a situation, instead of doing an iteration to execute the same process, you call the same function with the initial result. This process keeps running until the end result is achieved. The end result is determined by the condition.

This process is terminated when the end result is received. If this function is not terminated then it will run till infinite time.

 

Advantages of Recursion in C language

  1. When you solve a problem by recursion, you do not need to call the function repeatedly. You call the function only once and till the end result, it keeps calling itself.
  2. It is very difficult to solve problems through Iteration but in the recursion, the same problem is resolved very easily.

 

Structure of Recursive Function

The general structure of a recursive function is being given below.

return type myFunction(Parameters-list)
{
     statement 1;
     statement 2;
     ...
     statement N;
     myFunction(Arguments-list);  //Calling itself , Recursive process.
     ...
     other statements;

Disadvantages of Recursion in C language

Although recursion problem can be easily solved in a lesser code there are also some disadvantages of the recursive process. These are being given below.  
  1. Slower – Recursive programs are slow with ordinary programs. Recursive programs take more time than normal programs to call Function repeatedly to call and end result.
  2. Requires additional memory – Requires extra memory to execute recursive programs in comparison to ordinary programs.

 

Types of Recursion

Recursion in C language is of 2 types. Both types are being told from below.
 

Direct Recursion in C language

Direct recursion in C language is a recursion in which a function calls itself. The general structure of such recursion is being given below.
 
return_type MyFunction(parameter-list)
{
      ....statements;
      MyFunction(argument-list);
      .....other statements;

}

Indirect Recursion in C language

 

First Function

return_type FunctionOne(parameter-list)
{
     ....statements;
     FunctionTwo(argument-list);
     ....other statements;
}

Indirect recursion in C language is recursion in which a function calls another function which calls it back. The general structure of such recursion is being given below.

 
Second Function
 
return-type FunctionTwo(parameter-list)
{
       .....statements;
    FunctionOne(argument-list);
       .....other statements;
}

Example of Recursion (Factorial)

To illustrate recursion in C language by example, an example of factorial is being given here. From a factorial number 1 to any number of factorial you want to get, that number is the product (multiplication) of all numbers.

For example, you want to calculate factorial of 5. For this, you have to multiply all numbers from 1 to 5. After multiplying all the numbers, the result which will be achieved will become factorial of 5.

1 * 2 * 3 * 4 * 5 = 120

The c program can have two ways to calculate a number factorial.

  1. Using iteration – In this manner, you can run the loop from 1 to the given number and multiply all the numbers and then print the result.
  2. Using recursion – In this manner, you can create a function that multiplies the given number by a number less and calls itself with the same number.

Both of these methods are being explained through an example.

 

Calculating Factorial of a Number Using recursion in C language

/* factorialIteration.c */

#include <stdio.h>
int main()
{
    int num,i;
    int result=1;  
    printf("Enter number to find out its factorial.....");
    scanf("%d",&num);

   /* Iterating for loop to calculate factorial */

     for(i=1; i<=num; i++)
     result = result*i;
     printf("\nFactorial of %d is %d",num,result);
     return 0;
}
The above program produces the below-given output.
 
Enter a number to find out its factorial.
5
120
 

Calculating Factorial of a Number Using Recursion

/* factorialRecursion.c */
#include <stdio.h>
int MyFactFunction(int n);
int num;
int main()
{
    printf("Enter a number to find its factorial...");
    scanf("%d",&num);
    printf("Factorial of %d is : %d",num,MyFactFunction(num));
    return 0;
}
int MyFactFunction(num)
{
    if(num >= 1)        /* Function calling itself to calculate recursion */
        return num*MyFactFunction(num-1);
    else
        return 1;
}

In the example given above, MyFactFunction is a recursive function. It calls itself back with a number less than the given number and multiplies with the original value (with which the function was called).

This happens until the original value is greater than 1. As soon as this value becomes 1, this function gets terminate. This program generates the given output below.

Enter a number to find its factorial…

6

Factorial is : 720


Social Shares
  • 1
  •  
  •  
  • 1
  •  
  •  
  •  
  •  

2 comments

Leave a Reply

Your email address will not be published. Required fields are marked *