Recursion, Backtracking and Dynamic Programming
One of the foundational algorithms in advanced data structures and algorithms is backtracking. It is foundational to dynamic programming, and mastering it is essential for classical AI.
Most CS problems that involve dynamic programming uses backtracking as the basic algorithm.
Backtracking is intimidating at the beginning. The word backtracking sounds complex, and knowing that it is a pre-requisite to dynamic programming makes the complexity seem endless. Other words associated with backtracking problems, like combinatorics, path finding and graph problems also adds to the intrigue.
A pre-requisite for backtracking is recursion, which in itself is a mental hurdle for most of us. Backtracking is easy for those who are comfortable with recursion.
So, let’s start with a quick revisit of recursion.
Recursion
The recursive methodology is stepped-decomposition. The idea is to break a given problem into a slightly smaller problem, and repeat the process till it can’t be broken down any further.
There are two things expected from a recursive method:
- A base condition — This is typically an
ifcondition block, within which the smallest problem is solved and a value returned. This is the first thing we write in a recursive function. - A recursive call — This is the rest of the code, and executes only if the base condition fails. Typically, the method calls an instance of itself with a slightly smaller problem, a sub-problem that is marginally smaller than what it received.
This technique is extremely powerful and building an intuition for this technique is important before we move into backtracking.
Method Calls
Here are a few mental models that will help us write good recursive methods:
- The function code we write is a template. At the time of execution, it is an instance of the template that executes. This model is similar to writing a class in object oriented programming.
- Each time a function is called, a new and unique instance of the function is created with parameters that were passed to it.
- A function can simultaneously be called by many programs. Imagine a basic method like
print(), it can’t be true that it serves only one program at a time. This becomes possible because, like we learnt in the previous point, each caller is getting an instance of the function. - Each instance of a function lives in its own space in memory, and has its own life cycle.
- If a function has three lines of code, and only the second line is a function call, then the first line executes without any dependencies. The second line calls the function and waits for a return value. Until it gets the return value, it cannot execute the third line of code.
At this time, these points about method calls should seem obvious to you and natural. The next step is to analyze a concrete example. The most famous, and the simplest example is to find the factorial of a number.
A lot of us wonder why we cannot use a loop to solve this problem. We can, but the focus of this exercise is not to solve the factorial problem. It is to analyze the recursive methodology — let’s focus on that. The factorial problem was taken, because it is simple, and will not get in the way of our attempt to understand recursion. We will later look at other problems that are easier when solved with recursion.
To be on the same page, this is what factorial means:
3! we use the exclamation mark to indicate factorials;
it is pronounced "three factorial".
1! = 1 = 1
2! = 2 x 1 = 2
3! = 3 x 2 x 1` = 6
4! = 4 x 3 x 2 x 1 = 24
5! = 5 x 4 x 3 x 2 x 1 = 120
So, if we know the value of 4!
then calculating the value of 5! is easy.
5! = 5 x 4!
That pattern holds good all the time
So, in programmatic terms:
factorial(5) = 5 x factorial(4)
How do we know factorial(4)
factorial(4) = 4 x factorial(3)
How do we know factorial(3)
factorial(3) = 3 x factorial(2)
How do we know factorial(2)
factorial(2) = 2 x factorial(1)
How do we know factorial(1)
EVERYONE KNOWS THE VALUE OF 1! = 1So, here is a recursive method that solves the factorial problem.
public int factorial (int i){ // line #1
if (i == 1) return 1; // line #2
int sub_i = factorial(i-1); // line #3
return (i * sub_i); // line #4
} // line #5Note the name of the function in line #1, the function is called factorial. The above code is recursive; the factorial function is recursively calling itself on line #3.
It is hard to believe that this function will return the factorial value of an integer passed to it; but it does.
Leap of Faith: I have heard people say that we need to learn to have faith while learning recursion. What they mean is: trust that line #3 works and will give us the value we expect and build on that. To build a strong intuition, to build confidence in the methodology, we need to know how our code works.
So, we ask two questions:
1. Is the stepped logic correct? In our case, is it true that 3! = 3 x 2!
2. Where does it end? Is the base condition we wrote in line #2 correct?The first question is answered for us, we know the logic works, so let’s look at the second question, and to do that, let’s write down the stack for 3!
Let’s imaging that this is how the 3! function looks on the memory stack:
---------------------------------------------------------------------------
public int factorial (3){
if (3 == 1) return 1; // doesn't execute, because 3!= 1
int sub_i = factorial(2); // stops & waits here - for factorial(2)
return (3 x sub_i)
}
---------------------------------------------------------------------------This is the bottom-most on the recursive stack.
Now, there is another function call; another instance of the factorial function is called, and now, this is how the memory looks:
---------------------------------------------------------------------------
public int factorial (2){
if (2 == 1) return 1; // doesn't execute, because 3!= 1
int sub_i = factorial(1); // stops & waits here - for factorial(1)
return (2 x sub_i)
}
---------------------------------------------------------------------------
public int factorial (3){
if (3 == 1) return 1; // doesn't execute, because 3!= 1
int sub_i = factorial(2); // stops & waits here - for factorial(2)
return (3 x sub_i)
}
---------------------------------------------------------------------------Now, there are two instances of factorial(i) function on the recursive stack.
Note this moment: factorial(3) couldn’t complete, because it is waiting on factorial(2) — and factorial(2) couldn’t complete, because it is waiting on factorial(1). One could use the word stuck, but since this is by design, and we intended it this way, we will say: they are waiting.
Get Bharath Urs’s stories in your inbox
Join Medium for free to get updates from this writer.
Now, let’s see what happens inside factorial(1), which is the base case. The base case will not wait for any other function to complete execution, so we have artificially paused it just before it returns 1.
---------------------------------------------------------------------------
public int factorial (1){
if (1 == 1) return 1; // Returns 1, because 1 == 1
// these lines of code don't matter.
}
---------------------------------------------------------------------------
public int factorial (2){
if (2 == 1) return 1; // doesn't execute, because 2!= 1
int sub_i = factorial(1); // stops & waits here - for factorial(1)
return (2 x sub_i); // can't execute yet - waiting
}
---------------------------------------------------------------------------
public int factorial (3){
if (3 == 1) return 1; // doesn't execute, because 3!= 1
int sub_i = factorial(2); // stops & waits here - for factorial(2)
return (3 x sub_i); // can't execute yet - waiting
}
---------------------------------------------------------------------------Let’s un-pause, let’s allow the factorial(1) complete the execution: it does that by returning 1 and jumping off the stack, and into the oblivion.
This is how the stack looks now:
---------------------------------------------------------------------------
// factorial(1) used to live here before returning 1
// now this memory space is available for others
---------------------------------------------------------------------------
public int factorial (2){
if (2 == 1) return 1;
int sub_i = 1; // the wait is over - we got 1
return (2 x 1); // ready to return 2 x 1 // WE ARE PAUSED HERE
}
---------------------------------------------------------------------------
public int factorial (3){
if (3 == 1) return 1; // doesn't execute, because 3!= 1
int sub_i = factorial(2); // stops & waits here - for factorial(2)
return (3 x sub_i); // can't execute yet - waiting
}
---------------------------------------------------------------------------Let’s un-pause and let factorial(2) return 2 ; we will see this method jumping off the stack as well:
---------------------------------------------------------------------------
// factorial(1) used to live here before returning 1
// now this memory space is available for others
---------------------------------------------------------------------------
// factorial(2) used to live here before returning 2
// now this memory space is available for others
---------------------------------------------------------------------------
public int factorial (3){
if (3 == 1) return 1;
int sub_i = 2; // the wait is over - we got 2
return (3 x 2); // ready to return 3 x 2 // WE ARE PAUSED HERE
}
---------------------------------------------------------------------------When we un-pause from here, factorial(3) returns 6 — which is the correct answer for 3 x 2 x 1.
This works each time, as the last instance of the factorial function on the stack is factorial(1) which always returns 1 and in a chain of returns, all the function calls get what they were waiting for and stack of functions that were unfolded, all fold back to the original instigator of the chain.
This is the idea of recursion, and getting an intuition of this is empowering when we are dealing with backtracking.
Backtracking
The visual I used to remember backtracking when I heard of it the very first time was a meticulous robot trying every possible path to get to the other side of a maze. If one path doesn’t work, then take a step back and try the other path. If all the paths were taken, then take another step back and take the other path. If all of those have been tried, then take another step back and so on.
Let’s start by solving a few problems:
All Possible Subsets
Given an array A = [ 1, 2, 3 ] generate all possible subsets. In this case, we want to generate [ ], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3] as the answer to this question. N = 3 in this case, but N can be any number.
One way to think about generating all possible subsets is through exclusion/inclusion. At traverse the array, and at every element, we decide to either exclude or include the element for a subset. We notice this in the generated sets. In the first subset, everything is excluded; in the second, third and fourth, only one element is included; in the next three, only one element is excluded; and in the last set, all elements are included.
There are ways to manage a solution, but perhaps the easiest approach will be to use backtracking; let’s see how.
print_subset(Array temp); //prints all elements in a subset
create_subset([1, 2, 3], 0); // call the function
Array[] temp_subset = [];
void create_subset(Array A, int i){
if (i == 3) {
print_subset(temp_subset);
return;
}
// exclustion distributary
// we exclude by not doing temp_subset.add(A[i]);
create_subset(temp_subset, i+1);
// inclusion distributary
temp_subset.add(A[i]);
create_subset(temp_subset, i+1);
} In the code above, the create_subset() method prints the current state of the temp_subset if the index has gone beyond the end of the array. When it does that, it also returns to the caller method without further calling any recursive methods.
When that’s not the case, it has two decisions to take at every element: exclude and include;
Both these decisions have been baked into the code: First, I exclude the element and recurse, and when I get back the control, I include the element and recurse.
These decisions are recursively taken at every element. Irrespective of which element we speak, it has been excluded in one path and included in another path.
Every element is a starting point for two other distributaries. In our example, at the very beginning, [ ] is one distributary, and [1] is the other distributary. Now [ ] will continue on it’s path to make the exclude / include decision about the second element.
We have TWO distributaries:
[E]
[1]At the second element, [ ] will exclude 2 in one distributary and include it in the other, so, the two distributaries will look like this: [ , ] when it excludes 2 and and [ 2 ] when it includes. commas are used for clarity.
In the other distributary, [1] will exclude and include 2, a that will look like this: [1, ] and [1, 2]
These are the FOUR we have till now:
[E,E]
[E,2]
[1,E]
[1,2]Each of these will now make a decision about 3.
[E,E] excludes and includes 3, so, it will look like: [E,E,E], [E,E,3].
[E,2] will make the same decisions: so [E,2,E] and [E,2,3].
[1,E] will make the same decisions: [1,E,E] and [1,E,3].
[1,2] will make decisions to get: [1,2,E] and [1,2,3].
These are the EIGHT we have now:
[E,E,E] [E,E,3]
[E,2,E] [E,2,3]
[1,E,E] [1,E,3]
[1,2,E] [1,2,3]
// Re Written as:
[] [3] [2] [2,3] [1] [1,3] [1,2] [1,2,3] // in that orderThese subsets are generated in that order because of the way the methods recurse. We can re-order that, but we can clearly see that all the subsets have been generated.
So, to generalize the idea of Backtracking:
recursive_method() {
if (base_condition){
// do something if needed
// return to caller method
}
// the following happens when base_condition = false
Take path-1 of recursion
Undo path-1
Take path-2 of recursion
Undo path-2
..
...
Take path-N of recursion
}In our case, we didn’t need to un-do anything, because we chose to exclude-path first and then do the include-path.
If we had done the include path first, then it’s already included, so how do we exclude? we can do that by un-doing what we did in the include path.
