Exclusive Learning on Recursion in C Programming

Recursion is a mathematical term that stands for the repeated application of a method or definition. In programming terms, recursion is said to be done when a function calls itself directly or indirectly. The process is called recursion, and the created function is known as a recursive function.

Recursion in C Programming is an extremely important concept and recursive algorithms can help in solving difficult problems easily.

Recursion is extensively used in the C programming language. There are a lot of things that programmers have to keep in mind while using recursion. These things are discussed below. Read on to learn more.

Types of Recursion in C Programming

Recursion can be categorized into two types. These are – Direct Recursion and Indirect Recursion.

Direct Recursion

Direct recursion is the one in which a function calls itself from within itself. A simple explanation would be – you create a function, and you call the same function again inside it. Let us understand it through a code snippet.

Also Read: How to implement Strcpy and Strncpy function in C?

Example 1.1 sample (int n)

{

if (n<=1)

printf(“Good”);

else

return sample(n-1);

}

Example 1.2 sample (int n)

{

if (n<=1)

printf(“Good”);

else

return sample (n-1);

return sample (n-2);

}

Direct recursion itself is of four types. What is String in C programming? How to use it?

Tail Recursion in C Programming

When a recursive call is being made in the function, and the statement containing the call is the last statement inside the function, then it is known as Tail Recursion. Its example would be the snippet from Example 1.1

Head Recursion

Head recursion is the opposite of tail recursion which means that the recursive call is the first statement inside the function.

Also Read: What are Pointers in C programming?

sample(int n)

{

if (n>0)

{ sample(n-1); }

printf (“good”);

}

Linear Recursion

When a function is calling itself for one time, it is known as linear recursion. Refer to example 1.1

Also Read: How Double Pointer Works in C?

Tree Recursion

When a function is calling itself for more than one time, it is known as tree recursion. Refer to example 1.2

Indirect Recursion

This is the type of recursion in C programming where more than one functions call each other.

Example: Sample code snippet for indirect recursion: Two functions (funcA and funcB) are declared in the below-written example. funcA calling funB and funcB and funcB calling funcA.

Also Read: How Dangling Pointer affects your programming?

funcA(int n)

{

if(n>0)

{printf(“Good!”);

}

funcB(n-1);

}

funcB(int n)

{

if(n>1)

{printf(“Very good”);

}

funcA(n*2);

}

How to Use Recursion in C Programming?

C programming supports recursion and C programmers use recursion extensively to solve complex problems. Now let us come to a few basic things that you should know before solving a problem by using recursion.

While using C recursion, the solution to the main problem is divided into a base solution and a recursive function. To clear the meaning of the above statement, let us take an example:

int fact(int n)

{

if (n <= 1)

return 1;

else

return n*fact(n-1);

}

Let us understand the above piece of code.

Here, we are trying to find the factorial using recursion in C programming of n which is an integer. Now we all know that factorial of n is n*(n-1)*(n-2)*(n-3)*……*3*2*1. So what we are doing here is creating a function fact(int n).
Then, we are providing a solution for the smaller problem where n <= 1. This is the base solution. We know that factorial of 1 and 0 is 1. So if (n <= 1), we are asking the program to return 1.
Now the main problem arises. What if the value of n is greater than 1? So for larger values of n, what we are doing is calling the function inside itself. So what is basically happening here is the function is calling itself, but this time, for value n-1. The same thing will now happen to n-1. If (n-1 <= 1), 1 will be returned, and for larger values of n, the function will call itself for the value n-2. This will keep on happening for say, x times. Here, n – x becomes 1.
This is how a factorial of a number is found using recursion in C Programming.

So now you should have got the basic idea of recursion. What is happening here is, we are dividing the main problem into smaller problems using recursion, while also providing one or more base conditions to end the recursion.

Why are base conditions important? To end the recursion. If we do not provide any base condition or exit condition, an infinite loop will be started. Recursion has to end somewhere. So always remember to provide an exit condition while using recursion.

At the starting of this article, we mentioned that a function can make recursive calls directly or indirectly. What does this mean? Say there is a function fact. If “fact” calls “fact” then it will be a direct recursive call. If “fact” calls another function, say “fact1”, then it will be indirect recursion.

How is Recursion Useful?

Recursion in C Programming helps is solving big problems neatly and easily. The program that uses recursion is easy to read and understand. It is also very useful when we need to apply the same solution again.

Another advantage of using recursion is that the program can be small in comparison to its iterative solution which is long.

The examples of problems that can be solved using recursion are – finding factorial of a number, Fibonacci series, finding the sum of natural numbers. Using recursion is also very convenient while dealing with data structures like trees.

Are There Any Disadvantages of Recursion in C Programming?

Yes. We always have to provide an if condition as an exit condition to end the recursion otherwise it will enter an infinite loop.

Recursion also uses more processor and is a bit slow as compared to iterative methods and other methods.

Recursion also takes up a huge chunk of memory because it requires stack space each time it is invoked. This creates the problem of running out of space when dealing with lengthy problems.

Let us now take recursion in C examples and its applications in a better way.

A Program For the Sum of n Natural Numbers.

FlowChart

sum of n natural number using recursion in c

Algorithm

Start the Program
Function sum(int n) will be used to find the answer.
First, call the function main.
Declare num and answer as integers.
Get the value of num.
Write answer = sum(num) and print answer as “sum = %d”.
Now coming to the function sum(int n) – check for the condition
1. if n is not equals to 0, return n + sum(n-1).
2. Else, return n.
End the Program

Program

#include<stdio.h>
int sum(int n); //Declare sum Function
int main()
{
int num, answer; //Declare variables
printf (“Enter the positive integer of your choice\n”);
//printf(“Enter the positive integer of your choice:\n”);
scanf(“%d”, &num);
answer = sum(num); //Calling Sum Function
printf(“sum = %d”, answer);
return 0;
}
//Definition of sum function.
int sum(int n)
{
if(n!=0)
return n + sum(n-1);
else
return n;
}

Output

Explanation

Let us now understand the working of this program. Initially, the sum() function is being called from the main() function and we were passing num as an argument.

So what is happening here is that we are trying to find the sum of n natural numbers. The condition that is being checked is – n!=0 which means n does not equal to 0. Every time if the condition is true, the function will call itself again and will return – n + sum(n-1). So the value of n will keep on decreasing by 1 until it becomes 0. As soon as the value of n becomes 0, the if condition will become false and the else statement will be executed i.e. return n.

That’s it. This is how simple this problem becomes if we use recursion in C Programming.

Generate Fibonacci Series Using Recursion in C Programming

Algorithm

Start
Create function fibo(int)
In the main function, declare n and get n. N is the number of terms.
Run a for loop where if a variable i is less than n, then print fibo(i) to the screen.
End the main function.
Now define the fibo(int) function created earlier. Write the function as fibo(int x)
Inside the function, create an ‘if’ condition where if x is equals to 0 or 1, the function will return x, else the function will return fibo(x-1) + fibo(x-2)
End

Program

#include <stdio.h>
int fibo(int); //Declare fibo function
int main()
{
int n=10;//Declare number of terms you want in Fibonacci series
for(int i=0; i<n; i++)
{
printf(“%d “, fibo(i));
}
return 0;
}
//Definition of fibo function
int fibo(int x)
{
if(x==0||x==1)
{
return x;
}
else
return fibo(x-1)+fibo(x-2);
}

Output

Print nth Term of Fibonacci Series Using Recursion in C Programming

Before we construct the program for the Fibonacci series, let us understand what it is.

Theory

Fibonacci series is a series in which every number is the sum of the two numbers preceding it.

Example of Fibonacci series is – 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ………. Now let us take a look at the algorithm before we construct the program to print the nth number in the Fibonacci series.