What is the Recursion in C Language ??? with Free Notes

What is the Recursion in C ???

Recursion is derived from the words recur which means repetition. In C, it is possible for the function to call itself. Recursion is the process by virtue of which a function or a procedure can call itself. e.g.

fun()
{
    fun();
}

This means that function fun() is calling itself.

There are two Basics requirements for recursion:

1. The function must call itself again and again.
2. The Function must have an exit condition

Iterative Approach

The factorial of an integer n can be computed by the following iterative loop:

fact = 1;
for (i = 1; i<=n; i++)
      fact = fact*i;
  printf("\n The factorial of = %D = %D", n, fact);

Recursive Approach

We can also use an alternative approach of finding the factorial i.e.

n! = n*(n-1)!

So function f(n) is defined in terms of f(n-1). This type of definition is known as recursive definition. Now by the same definition the factorial of n-1 can be defined as

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

We can continue tis process till the end i.e. 0! which is equal to 1.

Thus algorithm for calculating the factorial n is expressed in terms of an algorithm for calculating the factorial n-1 and so on.

Th process described above can be implemented by using a function fact which is defined in terms of itself as shown in below:

fact(n) = { 1         if n = 0
            n* fact (n-1) if n>0

For example, we cab have a function fact which calls itself as below:

fact (int n)
{
    if(n ==0
         return(1);
   else
         return (n* fact(n-1));
}

The function fact is being called by itself but with parameter n being replaces by n-1. This ability of a function to call itself is known as recursion.

Free Programming E-Books

Example:

Let’s take an example of Recursion, In this example, write a program to compute factorial of a number using recursion.

/*Factorial of a number using recursion*/
/*Factorial of Given Number*/
#include <stdio.h>
#include <conio.h>
    void main()
            {
              int fact(int);   
              int num;
              clrscr();
              printf("\nEnter a number");
              scanf("%d", &num);
              f = fact(num);
              printf("\n The Factorial of %d = %d", num, fact(num));
                getch():
             }
              int fact (int n)
                 {
                   if (n==0)
                       return (1);
                   else
                       return (n*fact (n-1));
                 }

Output

Enter any Number 4 
The Factorial of 4 = 24

How Recursion works internally ???

if we have to compare 4! using recursion. The steps to be followed by the above program are:

1.     4! = 4.3!
2.           3! = 3.2!
3.                 2! = 2.1!
4.                     1! = 1.0!
5.                     0!= 1
6.                     1! = 1.1 = 1
7.                 2! = 2.1 = 2
8.           3! = 3.2 = 6
9.      4! = 4.6 = 24
 OR  it can be worked as below 
     fact (4) returns (4.fact(3)
         which returns (3.fact(2)
             which returns(2.fact (1)
                  which returns (1.fact(0)
                       which returns (1)))))

Special Notes:

Recursion can be used to write simple, short and elegant programs. However a recursive algorithm requires that must end the recursive calls. The absence of this condition would result in an infinite loop. For example, in function fact the condition “n==0” is the required terminating conditon.

Since recursion involves overheads such as CPU time and memory storage, it is suggested that recursion should be used with care.