Code360 powered by Coding Ninjas X Code360 powered by Coding Ninjas X
Table of contents
Recursion in Principle of Mathematical Induction (PMI)
Types of Recursion
Direct Recursion
Linear Recursion
Binary Recursion
Multiple Recursion
The Factorial Function
The Fibonacci Function
Recursion on Data Structures
Problems on Data Structures
Interview Problems Asked In Top Product Companies
Frequently Asked Questions
What are the topmost applications of recursion?
Does return statements are compulsory in recursion?
Can we solve every problem using recursion?
What is the base condition in recursion?
Last Updated: Mar 27, 2024

Recursion and Backtracking Algorithm With Practice Problem

Author Ravi Khorwal
0 upvote
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
Earn badges and level up


Have you at any point stuck in the circle of dreams called Fake Awakeness, where you think you emerged from a plan?

However, you’re not last; you come out when you have a stun or complex issue in a dream.

This is what Recursion means! You need to iterate through the loops until the condition fails. As a result, recursion has been a hot topic commonly asked in most top companies Flipkart, Google, Snapdeal, Walmart, and many more.

Recursion and Backtracking Algorithm

In programming, recursion is a method for handling an issue where the plan depends upon answers for more minor events of comparative cases.

Such matters can be addressed by cycle; however, these requirements recognize and file the more minor circumstances at programming time.

The methodology can apply to numerous kinds of issues, and recursion is one of the focal thoughts of software engineering.

The force of recursion lies in the chance of characterizing a boundless arrangement of articles by a limited assertion.

Additionally, a restricted recursive program can portray an infinite number of calculations, regardless of whether this program contains no express reiterations.

This recursiveness in a capacity or idea is firmly identified with the strategy known as numerical acceptance and is principal of significance in rationale and science. 

Must Read Recursive Binary Search.

Recursion in Principle of Mathematical Induction (PMI)

We have another exciting chapter on your way to relate recursion which is mathematical induction (PMI).

To prove PMI, we need three basic steps:

  • Step-1 (Base Case): Here, we make X=0 or X=1 to make the LHS and RHS accurate.
  • Step-2 (Induction Hypothesis): We need to assume that F(k) is accurate. It’s purely an assumption part.
  • Step-3 (Induction Step): Now, we need to prove the statement is true for X=k+1 with the help of step 2
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job

Types of Recursion

We can categorise the recursion into two types as

  • Direct recursion
  • Indirect recursion

Direct Recursion

When in the body of a method, there is a call to the same way, we say that the technique is directly recursive. Factorial and Fibonacci Series are the best examples of direct recursion.

We have three types of Direct Recursion. They are

  • Linear Recursion
  • Binary Recursion
  • Multiple Recursion

Linear Recursion

Linear recursion starts by testing for many base cases; there ought to be at least one base case or base condition in the function call.

In Linear recursion, we follow as under:

  • Play out a solitary recursive call. This recursive improvement may consolidate a test that picks several potential recursive calls to make. Yet, it ought to, eventually, decide to make only one of these calls each time we play out this development.
  • Characterize every conceivable recursion call so it gains ground toward a base case.
  • Ex: Factorial sums are the best examples of Linear recursion.

Binary Recursion

  • Binary recursion happens when we make two recursive calls to solve two independent smaller sub-problems in the same function.
  • Ex: To compute the N-th Fibonacci Term
    • Fibonacci Terms are solved by using a simple formula : F{n} = F{n-1} + F{n-2} with base values F(0) = 0 and F(1) = 1. Here, we clearly see that we have two independent calls to solve a bigger problem.

Multiple Recursion

  • We are within sight of different recursion when the actuation of a strategy can cause more than one recursive enactment of a similar technique.
  • Ex: Depth-first search is the most familiar example of multiple recursion.
  • Depth-first search is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node and explores as far as possible along each branch before backtracking.

The Factorial Function

Factorials can be built by a number by each number under it. Then, the interaction is utilized, and other things to track down the quantity of “n” items can be organized. Moreover, a factorial can be a recursive capacity as we can ascertain more huge numbers by computing factorials of lower numbers.

Ex: To calculate 5’s factorial, we have to multiply the natural numbers between 1 and 5, including. Which essentially means multiplying the literals(1 to 5) five times.

5! = 5 x 4!
4!=4 x 3!
3!=3 x 2!
2!= 2 x 1!
Therefore 5! is 120.

Practice more sums here at Coding Ninjas Studio.

Did I just say “Coding Ninjas Studio”? Probably, I need to explain this a little more.

So this platform is developed by highly talented people who have demonstrated work experience in different companies like Google, Microsoft, Amazon. Coding Ninjas Studio contains high-quality content for people preparing for tech interviews to get into product-based companies as Software Development Engineer(SDE1).

The Fibonacci Function

The many Fibonacci succession is a progression of numbers where a number expands the last two numbers, beginning with 0 and 1. The Fibonacci Sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21 … Written generally speaking, the articulation is: Yn = Yn-1 + Yn-2. All of the squares portray the space of the accompanying number in progression.

The Fibonacci turning is then drawn inside the squares by interfacing the edges of the compartments. The squares fit together impeccably because the proportion between the numbers in the Fibonacci succession is extremely near the brilliant proportion, which is around 1.61803…

The bigger the numbers in the Fibonacci arrangement, the nearer the proportion is to the brilliant proportion.  The twisting and coming about square shape are otherwise called the Golden Rectangle. Some of the top questions asked by leading companies on basic recursive are The nth term of GP and Tower of Hanoi

Also Read - Selection Sort in C  and Fibonacci Series in JavaScript

Recursion on Data Structures

Arrays and strings have enormous volume sums.

In Arrays, we have various kinds of arranging procedures like quicksort, mergesort, and selection sort. We likewise have other looking techniques like Linear Search and Binary Search as the vast majority of the sharp ear flavoring. 

Strings have various issues like removing a substring, adding and removing characters, reversing a string, removing duplicates, converting string to integer, and many more.

Data Structures are the core of developers to reduce the solution of huge linked lists, trees, Binary search trees, and significantly more in backtracking like sudoku, N-Queens, Paths in the maze, etc., and so forth.

Recursion is generally helpful in Data Structures. First, we break them into more modest aggregates and afterwards apply recursion to address the large one to tackle complex issues. 
Merge sort is used to sort the array elements.

For example, sort a given list of n natural numbers, split it into two lists of about n/2 numbers each, sort each of them in turn, and interleave both results appropriately to obtain the sorted version of the given list.

Must Read Recursion in Data Structure

Must Read Algorithm Types

Problems on Data Structures

Interview Problems Asked In Top Product Companies

These questions are the toughest of recursion and are frequently asked in product-based companies like Google, Microsoft, Amazon, etc.

Frequently Asked Questions

What are the topmost applications of recursion?

Recursion has its vast applications, but it helps calculate the agile score as agile is core for most software companies.

Does return statements are compulsory in recursion?

It’s not explicitly told to have a compulsory return statement in your recursive function, but having the return statement is better in your function.

Can we solve every problem using recursion?

No, recursion makes solving problems easier by breaking them into smaller sub-problems, making issues easier to understand. As such, not all problems can be broken down into smaller subproblems to be solved recursively.

What is the base condition in recursion?

The base condition is the possible minor problem in a significant issue that doesn’t require any functions to solve.


The focus is on recursion and types of recursion, with some examples. We saw how we could solve and approach the problems on recursion and backtracking.
We have also discussed a brief path to master recursion and different problems to practice on Arrays, Strings, Linked lists, trees, and top questions asked by different product-based companies like Google, Microsoft, and Snapdeal.

Also Read - Kadanes Algorithm

Permutation of string

To practice more sums on competitive coding, Interview problems, and guided paths for programming languages, Data Structures, and core subjects of Computer science at CodeStudio, you can refer to this document for customized problems.

Previous article
Generate all possible strings formed by replacing letters with given respective symbols
Next article
Stack in C++
Guided path
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
Earn badges and level up
Live masterclass