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.

  1. 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).
  2. 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.
  3. 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.
  4. 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

  1. Start the Program
  2. Function sum(int n) will be used to find the answer.
  3. First, call the function main.
  4. Declare num and answer as integers.
  5. Get the value of num.
  6. Write answer = sum(num) and print answer as “sum = %d”.
  7. 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.
  8. 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

recursion in c

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

  1. Start
  2. Create function fibo(int)
  3. In the main function, declare n and get n. N is the number of terms.
  4. Run a for loop where if a variable i is less than n, then print fibo(i) to the screen.
  5. End the main function.
  6. Now define the fibo(int) function created earlier. Write the function as fibo(int x)
  7. 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)
  8. 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

fibonacci series

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.

Flow Chart

Fibonacci Series using Recursion in C

Algorithm

  1. Start
  2. Create function fibo(int n).
  3. If the value of n is less than or equals to 1, then return n, else, return fibo(n-1) + fibo(n-2).
  4. Now get the value of n.
  5. Print the answer.
  6. Stop.

Program

#include<stdio.h>
//Definition of fibo function
int fibo(int n)
{
if (n <= 1)
return n;
else
return fibo(n-1) + fibo(n-2);
}

int main()
{
int n; //Declare variable ‘n’
printf(“Enter value of n: \n”);
scanf(“%d”, &n);
printf(“%d”, fibo(n)); //Calling function fibo
return 0;
}

Output

rcursion in C programming

Explanation

The first thing we do in this program is to create a recursive function. This function will make the compiler understand what the Fibonacci series is. If the value of n <= 1, the program will return n as it is, but if the value of n is greater than n, the program will return two numbers preceding it.

Now we come to the main program. We declare n as an integer and then ask the user to input the value of n. The program then runs the recursive function to print the output.

Find a Factorial of a Number Using Recursion in C Programming

Theory

The factorial of a number n is the multiplication of the number with the series of numbers preceding it till 1. Factorial of a number n will be represented as n!

This can be explained by an example. Let us take the number 6 and find its factorial. The factorial of 6 will be = 6*(6-1)*(6-2)*(6-3)*(6-4)*(6-5) = 6*5*4*3*2*1= 480

So the general formula to find the factorial of a number n is = 1*2*3*…….*n

Flow Chart

Find Factorial using recursion in C

Algorithm

  1. Start
  2. Create function facto(int n)
  3. If the value of n is less than or equals to 1, return 1, else, return n*facto(n-1).
  4. Declare n as an integer.
  5. Get the value of n.
  6. Print the answer.
  7. End

Program

#include<stdio.h>
//Definition of facto function
long int facto(int n)
{
if (n <= 1)
return 1;
else
return n*facto(n-1);

}

int main()
{
int n; //Declaration of variable n
printf(“Enter a positive integer to find its factorial: \n”);
scanf(“%d”, &n);
printf(“The factorial of the entered number is: %ld”, facto(n)); //Calling function facto
return 0;
}

Output

recursion in c programming

Explanation

We create a recursive function to explain to the compiler what factorial is. If the value of n <= 1, the program will return 1, but if the value of n is greater than 1, the program will return the product of the number and the numbers preceding it.

Now in the main program, we ask the user to input the value of n. Then the program will run the recursive function to print the answer.

Program on the Tower of Hanoi Recursion in C Programming

Theory

The Tower of Hanoi is a puzzle. Here, we have three rods and n number of disks. The disks are arranged in the form of a stack which has to be moved to another rod while following these rules:

  1. You can move one disk at a time.
  2. The only disk that can be moved is the one that is at the top of the stack.
  3. A disk cannot be placed on top of another disk which is smaller.

Algorithm

  1. Start
  2. Create a recursive function towhan.
  3. If the value of n equals to 1, print the step of disk movement from one rod to another.
  4. Else, return recursive function towhan for value n-1, then print the disc movements.
  5. Now get the number of disks from the user and use the recursive function to print the answer.
  6. End.

Program

#include<stdio.h>
//Declaration of Function towhan
void towhan(int n, char rodstart, char aux_rod, char rodend)
{
if (n==1)
{
printf(“First Disk  from %c to %c \n”, rodstart, rodend);
return;
}

towhan(n-1, rodstart, aux_rod, rodend);
printf( “another disk %d from %c  to %c \n”, n, rodstart, rodend);
towhan(n-1, aux_rod, rodend, rodstart);
}

int main()
{
int n;
printf(“Enter the number of disks: \n”);
scanf(“%d”, &n);
towhan(n, ‘A’, ‘C’, ‘B’); //Calling towhan function
return 0;
}

Output

output

Explanation

We create a function towhan to explain to the compiler what tower of Hanoi is. We declare three rods as characters. For the value of n==1, we print the steps of the disk movement (Move the disk from one rod to another). For values of n greater than 1, we call the function again for the disk n-1 and print the disk movement. We do it again for another set of rods.

Now we get the number of disks from the user. We name the rods as ‘A’, ‘B’, and ‘C’. Then print the steps using the function we created.

Hello, My Name is Abhinav. I am an Author in the Education Category of Trickyedu. I have Done My Engineering in Computer Science from DIT University. I have a good command on Science, Programming Language, and microprocessors. So, I choose this platform to share my knowledge and experience.

Leave a Comment