In this section, we will discuss a very important concept of programming languages called recursion that is extensively used in programming subjects like data structure and algorithms.

What is Recursion?

When a called function, in turn, calls another function which leads to a ‘chaining’ process of repetitions of function within a function, then this technique is called as recursion. Recursive call of a function is a special case of recursion, where a function calls itself.

A simple example to give an idea of recursion:

Explanation:

In line 2 of the above code, when outer function main() is called, it in turn, calls itself again inside it in line 5. This technique of a called function calling itself is called recursion. Hence, function main() is a recursive function.

Where can we use Recursive Functions?

• Recursive functions can be used more preferably than other known methods to solve problems that are based on successively applying the same solution to the subsets of the problem to find the final solution.
• In using a recursive function, we must use an if statement somewhere in the function to force the function to return without the recursive call being executed. Otherwise, the recursive function will go into an infinite loop and never return any value.
• Recursive functions are more clear and cleaner to write because of their structure and the sophisticated algorithm it uses to solve a problem. So it can be used in some places rather than using loops like problems on the Tower of Hanoi, Finding factorial, Fibonacci series, etc. However, recursive functions are slower in processing than loops.

How memory is allocated for Recursive Functions?

• When a called function, calls itself again inside its body, it marks the origin of the recursive call of the function.
• Then a new stack memory is allocated temporarily in which the data values are copied from the preceding function.
• After the working function returns a value, the stack gets de-allocated or self-destroyed.
• Then the recursive call moves to the next called function in line and it again creates a new stack memory for it.
• So for each call of a function, a separate stack memory is allocated with the same set of statements and declared variables used in preceding functions.
• This process continues until a terminating condition is encountered and the value, as well as the control of flow, is returned back to the initially called function.

Some examples of program using Recursion

Below are a few examples to demonstrate the use of recursive calls of functions.

Example: Program to find the sum of the range of numbers from 1 using recursion.

#include<stdio.h> 
int Sum(int);
int main() 
{
   int N;
   int Total;
   printf("Enter any number after 1: ");
   scanf("%d",&N);
   Total=Sum(N); 
   printf("\nSum of all the numbers from 1 to %d is %d.\n",N,Total);
   return (0);
}
int Sum(int N) 
{
   int Total;
   if (N==1) 
   {
    return (1);
   }
   else 
   {
    Total=N+Sum(N-1);
   }
  return (Total);
}

Output:

Enter any number after 1: 4
Sum of all the numbers from 1 to 4 is 10.

Example: Program to find the factorial of a number using recursion.

#include<stdio.h>
int factorial(int);
int main()
{
  int fact,number;
  printf("Enter a number: ");
  scanf("%d",&number); 
  fact=factorial(number);
  printf("Factorial of %d is %d\n",number,fact);
  return 0;
}
int factorial(int number)
  {
    int fact;
    if (number==1)
    {
      return(1);
    }
    else
    {
      fact=number*factorial(number-1);
      return (fact);
    }
  }

Output:

Enter a number: 4
Factorial of 4 is 24

Example: Program to print even and odd numbers in a range using recursion.

#include <stdio.h>
void EvenOdd(int InitialVal,int Num);
int main()
{
    int Num;	
    printf("Enter any number after 1: ");
    scanf("%d",&Num); 
    printf("\nEven numbers from 1 to %d are: ",Num);
    EvenOdd(2,Num);
    printf("\nOdd numbers from 1 to %d are: ",Num);
    EvenOdd(1,Num);
    printf("\n\n");
    return 0;
}
void EvenOdd(int InitialVal, int Num)
{
    if(InitialVal > Num)
        return;
    printf("%d  ",InitialVal);
    EvenOdd(InitialVal+2,Num);
}

Output:

Enter any number after 1: 5
Even numbers from 1 to 5 are: 2 4 
Odd numbers from 1 to 5 are: 1 3 5

In the next section, we will discuss the scope, visibility, and longevity of Storage Class of variables used in C.