Prashant | Wed, 26 Aug, 2020 | 133

In this chapter, we are going to see one of the most important topics which we are going to use throughout the sessions, i.e. Recursion and along with that, we are going to see its relative Backtracking.

Any function which calls itself is called recursive. A recursive method solves a problem by calling a copy of itself to work on a smaller problem. This is called the recursion step. The recursion step can result in many more such recursive calls.

It is important to ensure that the recursion terminates. Each time the function calls itself with a slightly simpler version of the original problem. The sequence of smaller problems must eventually converge on the base case.

Recursion is a useful technique borrowed from mathematics. Recursive code is generally shorter and easier to write than iterative code. Generally, loops are turned into recursive functions when they are compiled or interpreted.

Recursion is most useful for tasks that can be defined in terms of similar subtasks. For example, sort, search, and traversal problems often have simple recursive solutions.

Now we are going to see, How recursion works and how to write it in codes.

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

```
//sample test code for factorial of a number
int fact(int n)
{
if (n < = 1) // base case
return 1;
else
return n*fact(n-1);
}
```

In this we can see that, to find a factorial of a number we need to multiply to its lower number until 1, Such as we get n=5, then we have to find like 5x4x3x2x1. So each time we are doing or repeating the same function that decrease by one and multiply to the previous results until it becomes as small as 1.

So "1" is the base condition here. Also called stopping condition, as we need a stopping condition else loop will run infinitely.

Each recursive call makes a new copy of that method (actually only the variables) in memory. Once a method ends (that is, returns some data), the copy of that returning method is removed from memory. The recursive solutions look simple but visualization and tracing take time.

While discussing recursion, the basic question that comes to mind is: which way is better? – iteration or recursion? The answer to this question depends on what we are trying to do. A recursive approach mirrors the problem that we are trying to solve. A recursive approach makes it simpler to solve a problem that may not have the most obvious of answers. But, recursion adds overhead for each recursive call (needs space on the stack frame).

- Terminates when a base case is reached.
- Each recursive call requires extra space on the stack frame (memory).
- If we get infinite recursion, the program may run out of memory and result in a stack overflow.
- Solutions to some problems are easier to formulate recursively.

- Terminates when a condition is proven to be false.
- Each iteration does not require extra space.
- An infinite loop could loop forever since there is no extra memory being created.
- Iterative solutions to a problem may not always be as obvious as a recursive solution.