In this article we will learn about an interesting topic – recursion.

Difficulty level:Medium

Recursion is nothing but the act of repeating. In programming world, this is the same with a slight difference. Recursion is nothing but calling a function itself over and over again. Let’s dig deeper into the topic to get to know more!

Table of Contents

**What is Recursion?**

The process in which a function calls itself directly or indirectly is called recursion and the corresponding function is called as recursive function. Certain problems can be solved quite easily Using a recursive algorithm, Examples of such problems are Towers of Hanoi (TOH), Inorder/Preorder/Postorder Tree Traversals, DFS of Graph, Binary Search etc.

**What is base condition in recursion?**

The solution to the base case is provided in the recursive program and the solution of the bigger problem is expressed in terms of smaller problems

int fact(int n)

{

if (n < = 1) // base case

return 1;

else

return n*fact(n-1);

}

In the above example, base case for n < = 1 is defined and larger value of number can be solved by converting to smaller one till base case is reached.

**S**olving Problem** using recursion?**.

The idea is to represent a problem in terms of one or smaller problems, and add one or more base conditions that stop the recursion. For example, we compute factorial n if we know factorial of (n-1). The base case for factorial would be n = 0. We return 1 when n = 0.

## Example

Now let’s see Fibonacci series sum up with recursion.

### Code

```
int fib ( int location )
{
if ( location < 2 )
{
return 1;
}
else
{
return fib(location - 1) + fib(location - 2);
}
}
```

### Explanation

- First, we must know the last number in the series(till we want to print).
- That is taken as location. If it is less than 2, the only number would be 1.
- Now if the number is greater than 2, apply the condition fib(location-1)+fib(location-2).(this is the standard form for finding the sum of the fibonacci series)
- Once, the number goes less than zero, the recursion stops.

### Time complexity

Time Complexity T(n) = T(n-1) + T(n-2) which is exponential.

### Space Complexity

O(n) if we consider the function call stack size, otherwise O(1).

**Why Stack Overflow error occurs?**

Stack overflow problem may arise If base case is not reached. Let us take an example to understand this.

```
int fact(int n)
{
// wrong base case (it may cause
// stack overflow).
if (n == 100)
return 1;
else
return n*fact(n-1);
}
```

If fact(10) is called, it will call fact(9), fact(8), fact(7) and so on but number will never reach 100. So, the base case is not reached. Stack overflow error occur If the memory is exhausted by these functions on the stack, it will cause

**A**llocation of memory in recursion

When any function is called from main(), the memory is allocated to it on stack. A recursive function calls itself, the memory for called function is allocated on top of memory allocated to calling function and different copy of local variables is created for each function call. When the base case is reached, the function returns its value to the function by whom it is called and memory is de-allocated and the process continues.

Let us take the example how recursion works by taking a simple function

```
void printFun(int test)
{
if (test < 1)
return;
else
{
print test;
printFun(test-1); // statement 2
print test;
return;
}
}
// Calling function printFun()
int test = 3;
printFun(test);
Output :
3 2 1 1 2 3
```

When **printFun(3)** is called from main(), memory is allocated to **printFun(3)** and a local variable test is initialized to 3 and statement 1 to 4 are pushed on the stack as shown in below diagram. It first prints ‘3’. In statement 2, **printFun(2)** is called and memory is allocated to **printFun(2)** and a local variable test is initialized to 2 and statement 1 to 4 are pushed in the stack. Similarly, **printFun(2)** calls **printFun(1)** and **printFun(1)** calls **printFun(0)**. **printFun(0)** goes to if statement and it return to **printFun(1)**. Remaining statements of **printFun(1) **are executed and it returns to **printFun(2)** and so on. In the output, value from 3 to 1 are printed and then 1 to 3 are printed. The memory stack has been shown in below diagram.

When **printFun(3)** is called from main(), memory is allocated to **printFun(3)** and a local variable test is initialized to 3 and statement 1 to 4 are pushed on the stack as shown in below diagram. It first prints ‘3’. In statement 2, **printFun(2)** is called and memory is allocated to **printFun(2)** and a local variable test is initialized to 2 and statement 1 to 4 are pushed in the st

**Disadvantage / Advantag**e

Note that both recursive and iterative programs have same problem solving powers, i.e., every recursive program can be written iteratively and vice versa is also true. Recursive program will remain in stack until base case is reached hence has greater space requirements than iterative program as all functions . It also has greater time requirements because of function calls and return overhead.

Recursion provides a clean and simple way to write code. Some problems are inherently recursive like tree traversals, Tower of Hanoi, etc. Recursive case is preferred for this type of problem We can write such codes also iteratively with the help of the stack data structure.

## Conclusion

In this article, we learnt about the definition of recursion, some examples and its explanation, time complexity, and space complexity. We also discussed its advantage and disadvantage. Even it may confuse at first, we can get better by repeated practice. Never stop learning and start growing. Hope this article helped you learn in an easy way.

Leave us your comment below to let us know if you have any query!