After learning the concept of functions and how they are executed, it is time to understand recursion.
In this tutorial, you will learn all the basics of recursion in the data structure, different types of recursion in C language and some important interview questions asked.
Table of Contents
In simple English, recursion means repetition. In programming languages, recursion means the nesting of function calls.
In simple terms, recursion is writing a function call in its definition.
Or as Yashavant Kanetkar says,
A function is called recursive if a statement within the body of a function calls the same function.
Let us understand the concept of recursion by taking an example of the Fibonacci series.
It is a sequence of numbers in which every next term is the sum of the previous two terms. However, this logic doesn’t apply to the first two terms of the sequence.
The first two terms are initialized as 0 and 1.
The series looks like 0, 1, 1, 2, 3, 5, 8, 13, 21,…
A program that generates a Fibonacci series using a for loop is given below.
It uses a loop to add the last two terms to calculate the next term.
#include<stdio.h>
int main()
{
int i, first=0, second=1, next, j;
printf("Fibonacci example using loop\n");
printf("Enter number of terms\n");
scanf("%d",&i);
printf("Fibonacci series of %d terms is:\n",i);
for(j=0; j<i; j++)
{
if (j<=1)
next=j;
else
{
next=first+second;
first=second;
second=next;
}
printf("%d\n",next);
}
return 0;
}
Output:
Fibonacci example using loop Enter number of terms: 10 Fibonacci series of 10 terms is: 0 1 1 2 3 5 8 13 21 34
Now, the same program can be developed using the concept of recursion.
This method involves calling the function ‘fibo’ in its own definition.
#include<stdio.h>
int fibo(int);
int main()
{
int t, n=0, m;
printf("Fibonacci example using recursion\n");
printf("Enter number of terms:\n");
scanf("%d",&t);
printf("Fibonacci series for %d terms is:\n",t)
for(m=1; m<=t; m++)
{
printf("%d\n", fibo(n));
n++;
}
return 0;
}
int fibo(int n)
{
if(n==0||n==1)
return n;
else
return(fibo(n-1) + fibo(n-2));
}
Output:
Fibonacci example using recursion Enter number of terms: 10 Fibonacci series of 10 terms is: 0 1 1 2 3 5 8 13 21 34
It is the type of recursion that can be converted into a loop.
We have already seen the Fibonacci series example which can be programmed with recursion and loop.
It is a primitive recursion in which the recursive call is present as the last thing in the function.
In the above Fibonacci example, the recursive function is executed as the last statement of the ‘fibo’ function.
It is the type of recursion when there is only one recursive call in the function.
As by its name, it is the type of recursion when there are multiple recursive calls in the function.
It is just the opposite of a single recursion. Recursion can be either single or multiple types.
There are two or more functions involved in this type of recursion.
In this type of recursion, a function calls another function, which eventually calls the original function.
If there is a function that cannot be defined without recursion, is called general recursion.
It is the opposite of primitive-type recursion.
These are the different types of recursion in C.
What is the difference between tailed and non-tailed recursion?
In tail recursion, a recursive call is executed at the end of the function. If the recursive call is executed at the beginning or in the middle of the function, it is called a non-tailed recursion.
How the memory is allocated to the recursive function call?
When the recursive function gets called, the memory is allocated in stack memory. For every recursive function call, a copy of all local variables in the function is created.
After executing the recursive function, it returns the value to the function by whom it is called and memory gets deallocated from the stack.
What is the disadvantage of recursion?
The memory is incremented by the number of times a recursive function is called. This is one of the drawbacks/disadvantages of recursion.
When to (not) use recursion?
If memory utilization is the concern of if there is limited memory resource available, it is always a good choice to implement primitive type recursion with loops.
Mobile has very limited memory space to execute any apps. If you are developing a mobile application, avoid using recursion.
There are so many coding questions where you can implement recursion. Here is some of the basic questions you can practice.
Find more interview coding questions for practice.
Some of the advanced programs for practicing recursion:
This is all about different types of recursion in C. I am sure, this tutorial will help you understand every basic concept of it. If you have any questions, feel free to comment below.
Tarshal is a tech-head CS undergrad, who is always on the lookout for the sharpest cutting edge techs in the business, be it Blockchain, hashgraphs or AI/ML. With a knack for business development, negotiation and tech, she is often found educating those around her.