1.
Introduction
2.
Recursion
2.1.
Pseudo Code of Recursion
2.2.
Explanation
2.3.
The time complexity of recursion
3.
Backtracking
3.1.
Application of Backtracking
3.2.
The time complexity of Backtracking
4.
4.1.
How many times function Fibonacci() invoked in N = 4?
4.2.
What is the time complexity of the recurrence relation?
4.3.
How can we implement Backtracking?
4.4.
Are recursion and backtracking different?
4.5.
What is the base condition in Recursion?
5.
Key Takeaways
Last Updated: May 21, 2024

# Recursion & Backtracking Time Complexity

Ujjawal Gupta
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

## Introduction

This blog will discuss the time complexity of Recursion and backtracking. Recursion and Backtracking based coding problems are widely asked in various coding contests and various interviews.

## Recursion

The process in which a function calls itself directly or indirectly is known as Recursion, and the function which calls itself is known as a recursive function. You can learn more about recursion here. In function, there must be a base condition to terminate the recursive call of the function.

### Pseudo Code of Recursion

Let's write the pseudo code to find the Nth Fibonacci number using recursion to know how recursion works.

``````int Fibonacci(int n){

/*Base Condition*/
if(n==1 or n==0) return 1;

/*Recursive Call*/
return Fibonacci(n-1) + Fibonacci(n-2);
}``````

### Explanation

For any integer ‘N’, the function calls itself two times i.e, for ‘N-1’ and ‘N-2’. In this way, the recursive call expands until (like a tree) the value of ‘N’ is greater than 1, which is also the base condition to terminate the recursive call. Below is the recursive tree for N = 4.

### The time complexity of recursion

The time complexity of recursion depends on the number of times the function calls itself. If a function calls itself two times then its time complexity is O(2 ^ N). if it calls three times then its time complexity is O(3 ^ N) and so on.

Also check out - Rod Cutting Problem and Rabin Karp Algorithm

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
Bootcamp

## Backtracking

Backtracking is a technique used to solve the problems in which we need to build all the possible solutions and remove those solutions that fail to satisfy the problem's constraints at any point in time. You can learn more about backtracking here.

### Application of Backtracking

The following types of problems can be solved using backtracking

• All those problems where we need to find a feasible solution.
• Optimization problems.
• Problems in which we need to find all the possible solutions.

### The time complexity of Backtracking

The time complexity of backtracking depends on the number of times the function calls itself.

For example, if the function calls itself two times, then its time complexity is O(2 ^ N), and if it calls three times, then O(3 ^ N) and so on. Hence the time complexity of backtracking can be defined as O(K ^ N), where ‘K’ is the number of times the function calls itself.

Also see, Morris Traversal for Inorder.

### How many times function Fibonacci() invoked in N = 4?

There is a total of 9 times the function Fibonacci() invoked as there are eight recursive calls.

### What is the time complexity of the recurrence relation?

The time complexity 𝑇(𝑛)T(n) is given by the recurrence relation 𝑇(𝑛)=𝑇(𝑛−2)+𝑂(1)T(n)=T(n−2)+O(1), where 𝑇(1)=𝑐T(1)=c.

### How can we implement Backtracking?

Backtracking can be implemented using Recursion. With the help of recursion, backtracking generates all the possible solutions of any problem.

### Are recursion and backtracking different?

No, recursion is the process in which a function calls itself whereas backtracking is the technique that is implemented using recursion.

### What is the base condition in Recursion?

Base condition is the condition where the recursive call terminated. For example, in the Fibonacci number, the base condition occurs when the value of ‘N’ is less than or equal to 1.

## Key Takeaways

In this blog, we learned the concepts of recursion and backtracking. After that, we saw how backtracking is implemented using recursion and the time complexity of backtracking. You can practice problems Recursive multiplyCombination sum 2Word Ladder.

Hence learning never stops, and there is a lot more to learn.