• Home
  • Subscribe
  • Contribute Us
    • Share Your Interview Experience
  • Contact Us
  • About
    • About CSEstack
    • Campus Ambassador
  • Forum & Discus
  • Tools for Geek
  • LeaderBoard
CSEstack

What do you want to Learn Today?

  • Programming
    • Tutorial- C/C++
    • Tutorial- Django
    • Tutorial- Git
    • Tutorial- HTML & CSS
    • Tutorial- Java
    • Tutorial- MySQL
    • Tutorial- Python
    • Competitive Coding Challenges
  • CSE Subject
    • (CD) Compiler Design
    • (CN) Computer Network
    • (COA) Computer Organization & Architecture
    • (DBMS) Database Management System
    • (DS) Data Structure
    • (OS) Operating System
    • (ToA) Theory of Automata
    • (WT) Web Technology
  • Interview Questions
    • Interview Questions- Company Wise
    • Interview Questions- Coding Round
    • Interview Questions- Python
    • Interview Questions- REST API
    • Interview Questions- Web Scraping
    • Interview Questions- HR Round
    • Aptitude Preparation Guide
  • GATE 2022
  • Linux
  • Trend
    • Full Stack Development
    • Artificial Intelligence (AI)
    • BigData
    • Cloud Computing
    • Machine Learning (ML)
  • Write for Us
    • Submit Article
    • Submit Source Code or Program
    • Share Your Interview Experience
  • Tools
    • IDE
    • CV Builder
    • Other Tools …
  • Jobs

6 Different Types of Recursion in C Explained with Programming Example

Tarshal Nimawat/40194/0
C / C++CodeCSE SubjectData Structure

After learning the concept of functions and how they are executed, it is a time to learn recursion.

In this tutorial, you will learn all the basic of recursion in the data structure, different types of recursion in C language and some important interview questions asked.

Table of Contents

  • What is recursion in data structure?
  • What is the Fibonacci series?
    • Fibonacci C Program using Loop
    • Fibonacci C Program using Recursion
  • What are the different types of Recursion in C?
    • 1. Primitive Recursion
    • 2. Tail Recursion
    • 3. Single Recursion
    • 4. Multiple Recursion
    • 5. Mutual Recursion or Indirect Recursion)
    • 6. General Recursion
  • Interview Questioned asked about recursion
  • Recursion Program for Practice

What is recursion in data structure?

In simple English, recursion means repetition. And in programming languages, recursion means 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.

What is 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.

First two terms are initialized as 0 and 1.

The series looks like 0,1,1,2,3,5,8,13,21,……….

Fibonacci C Program using Loop

A program that generates Fibonacci series using for loop is given below.

It uses for loop to add the last two terms in order 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.

Fibonacci C Program using 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

What are the different types of Recursion in C?

1. Primitive Recursion

It is the types of recursion that can be converted into a loop.

We have already seen the Fibonacci series example which can be programmed with recursion as well as with loop.

2. Tail Recursion

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.

3. Single Recursion

It is the types of recursion when there is only one recursive call in the function.

4. Multiple Recursion

As by its name, it is the types 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 type.

5. Mutual Recursion or Indirect Recursion)

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.

6. General Recursion

If there is a function which cannot be defined without recursion, is called as general recursion.

It is the opposite of primitive type recursion.

These are the different types of recursion in C.

Interview Questioned asked about recursion

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 as 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 the all local variable 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 deallo0ctaed 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 the memory utilization is the concern of if there is limited memory resource available, it is always a good choice implementing 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.

Recursion Program for Practice

There are so many coding questions where you can implement recursion. Here is some of the basic question you can practice.

  • Write a program to find the length of the string using recursion.
  • Write a program to concatenate string using recursion.
  • Check if the given string is a palindrome or not using recursion.

Find more interview coding questions for practice.

Some of the advance program for practicing recursion:

  • Write a program to reverse the linked list element using recursion.
  • Binary tree traversal using 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 any question, feel free to comment below.

cpprecursion
Tarshal Nimawat
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.

Your name can also be listed here. Got a tip? Submit it here to become an CSEstack author.

Leave a Reply Cancel reply

C Programming

  1. C- Introduction
  2. C- Compile & Execute Program
  3. C- Data Types
  4. C- if-else statement
  5. C- While, do-while, for loop
  6. C- Array
  7. C- Function (Types/Call)
  8. C- strlen() vs sizeof()
  9. C- Nested Switch Statement
  10. C- Recursion
  11. C- Dynamic Programming
  12. C- Storage Classes
  13. C- Creating Header File
  14. C- Null Pointer
  15. C- Stack and Queue
  16. C- Implement Stack using Array
  17. C- Implement Linked List in C
  18. C- File Handling
  19. C- Makefile Tutorial

Object Oriented Concepts in C++

  • C++: C vs OOPs Language
  • C++: Introduction to OOPs Concepts
  • C++: Inheritance

Sorting Algorithms

  • Different Types of Sorting Algo
  • Selection Sort
  • Bubble Sort
  • Quick Sort

Programming for Practice

  1. Online C/C++ Compiler

String Handling:

  1. Remove White Spaces from String
  2. Implement strstr Function in C
  3. Convert String to Int – atoi()
  4. Check if String is Palindrome
  5. Check if Two Strings are Anagram
  6. Split String in using strtok_r()
  7. Undefined reference to strrev

Array:

  1. Check if Array is Sorted

Bit Manipulation:

  1. Count Number of 1’s in Binary

Linked List:

  1. Reverse a Linked List Elements

Number System:

  1. Program to Find 2’s Complement
  2. Convert Decimal to Binary in C

Tricky Questions:

  1. Add Two Numbers without Operator
  2. Find Next Greater Number
  3. Swap values without temp variable
  4. Print 1 to 100 without Loop

Interview Coding Questions

  • 50+ Interview Coding Questions

© 2022 – CSEstack.org. All Rights Reserved.

  • Home
  • Subscribe
  • Contribute Us
    • Share Your Interview Experience
  • Contact Us
  • About
    • About CSEstack
    • Campus Ambassador
  • Forum & Discus
  • Tools for Geek
  • LeaderBoard