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.
Must Read Recursion in Data Structure And Application of Graph in Data Structure
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
24+ registered 
