**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__