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):