Introduction to Recursion & Backtracking

Introduction

Backtracking is a general algorithmic technique that considers searching every possible combination order to solve an optimization problem. Backtracking is also known as a depth-first search or branch and bound. The Recursion technique is always used to solve backtracking problems. Let’s start first with Recursion.

Recursion

When a function calls itself, it is called Recursion. We can use the example of the movie Inception (dir. Christopher Nolan, 2010) to understand this. The lead in the film, played by Leonardo DiCaprio had a dream, and in that dream, he had another dream, in which he had yet another dream, and so on. Recursion is just like that: there is a function called dream() and we are just calling it in itself.

function dream()
{
   print "Dreaming":
   dream();
}

Recursion is useful in solving problems that can be broken down into smaller problems of the same kind. There are several things to be taken care of when using Recursion.

Let’s take a simple example and try to understand it. The following is the pseudocode of finding the factorial of a given number X using Recursion:

function factorial(x)
{
   if (x == 0) // base case
      return 1;
   else
      return x*factorial(x - 1); // break into smaller problems
}

The following slides show how it works for factorial(5):

Base cases

Any recursive method must have a terminating condition. The terminating condition is one for which the answer is already known, and we just need to return that. For example, for the factorial problem, we know that factorial(0) = 1, so when x is 0, we simply return 1; otherwise, we break it into smaller problems and find the factorial of (x - 1). If we don’t include a base case, the function will keep calling itself and will ultimately result in a stack overflow. For example, the dream() function discussed above has no base case. If you write a code for it in any language, it will give a runtime error.

Rules for the recursive call

There is an upper limit to the number of recursive calls that can be made. To prevent this from happening, make sure that your base case is reached before the stack size limit exceeds. So if we want to solve a problem using Recursion, we need to make sure the following points:

• the problem can be broken down into smaller problems of the same type,
• the problem has some base case(s),
• the base case is reached before the stack size limit exceeds.

Backtracking

When we solve a problem using Recursion, we break the given problem into smaller ones. Let’s say we have a problem PROB, and we divide it into three smaller problems P1, P2, and P3. It may be the case that the solution to PROB does not depend on all the three sub-problems. In fact, we don’t even know which one of the three it depends on.

Let’s take a situation. Suppose, you are standing in front of three tunnels. One of these has a bag of gold at its end, but you don’t know which one. So, you’ll try all three tunnels. First, go into tunnel 1, and if that is not the one, then come out of it. Then, go into tunnel 2 and if that is not the one either, come out of it. Finally, go into tunnel 3. So basically, in Backtracking, we attempt to solve a sub-problem, and if we don’t reach the desired solution, we undo whatever we did for solving that sub-problem and try solving another sub-problem.

Basically, Backtracking is an algorithmic paradigm that tries different solutions until a solution is found that works. Problems that are typically solved using the Backtracking technique can only be solved by trying every possible configuration and each configuration is tried only once. We can solve this by using Recursion.