Backtracking

Contents

Recursion

Chapter 1 : Recursion

Backtracking is a simple, yet elegant, recursive technique which can be put to a variety of uses. In this article, we will explore this technique in detail, and analyze its usefulness in tree spanning. We will also take an inside look into a sample game 'Mysterious Maze', which uses a depth-first algorithm to span a decision tree in order to dynamically generate mazes. First of all, however, let us discuss the basic principles of recursion, on which backtracking, as well as the more sophisticated algorithms we will be covering later, depend on.

Understanding Recursion

The factorial of an integer N (written as N!), is defined as N multiplied by all the integers lower than N. Thus 5! is calculated as 5 x 4 x 3 x 2 x 1 = 120. Let us examine a simple function that takes a single integer parameter and returns the factorial of that integer.

function fact(N){

var retval=1;
for(i=N;i>0;i--){
	retval=retval*i;
	}
return retval;
}

The loop is pretty straightforward. retval starts off with the value 1, is then multiplied by N, then N-1, and similarly all the integers between N and 1, inclusive. Now, let us write the same function in a slightly different way.

function fact(N){

if(N==1)
	return 1
else
	return N*fact(N-1)
}

Elegant, is it not? The algorithm takes advantage of the fact that the factorial of any integer N can be defined as the product of N and the factorial of N-1. For example 5! = 5 x 4!. The function above is an example of a recursive function, because, as you can see in the second 'return' statement, the function calls itself.

Recursive functions are closely related to inductive definitions of functions in mathematics. In order to evaluate whether an algorithm is a candidate for recursion, we must first try to deduce an inductive definition of the algorithm. For example, the factorial function can be defined inductively in this way :

		1 if N=1	
	N! =
		N x (N-1)! if N>1

Algorithms that are by nature recursive, like the factorial example above, can be coded either as a loop, as in the first example, or as a recursive function, as in the second example. However recursive functions are generally smaller and more efficient than their looping equivalents.

The Stack

The Stack is an special area of memory in which temporary variables are stored. The Stack acts on the LIFO (Last In First Out) principle, which is the same principle involved in, say, the stacking of cardboard boxes one atop the other, where the topmost box, which was the last box stacked (Last In), will the the first to be removed (First Out). Thus, if the values 9,3,2,4 are stored (Pushed) on the Stack, they will be retrieved (Popped) in the order 4,2,3,9. In order to understand how recursive functions use the Stack, we will walk through how the second algorithm above works. For your convenience, it is reproduced below.

if(N==1) return 1
else return N*fact(N-1)

Let us assume we want to find the value of 3!, which is 3 x 2 x 1 = 6. The first time the function is called, N holds the value 3, so the else statement is executed. The function knows the value of N, but not of fact(N-1), so it pushes N (value=3) on the stack, and calls itself for the second time with the value 2. This time round too the else statement is executed, and N (value=2) is pushed on the stack as the function calls itself for the third time with the value 1. Now the if statement is executed as n==1, so the function returns 1. Since the value of fact(1) is now known, it reverts back to it's second execution by popping the last value (2) from the stack and multiplying it by 1. This operation gives the value of fact(2), so the function reverts to it's first execution by popping the next value (3) from the stack, and multiplying it with fact(2), giving the value 6, which is what the function finally returns.

From the above example, we see that

The function runs 3 times, out of which it calls itself 2 times. The number of times that a function calls itself is known as the recursive depth of that function.
Each time the function calls itself, it stores one or more variables on the Stack. Since the Stack holds a limited amount of memory, functions with a high recursive depth may crash because of non-availability of memory. Such a condition is known as Stack Overflow.
Recursive functions usually have a terminating condition. In the above example the function stops calling itself when n==1. If this condition were not present, the function would keep calling itself with the values 3,2,1,0,-1,-2... and so on for infinity. This condition is known as Endless Recursion.
All recursive functions go through 2 distinct phases. The first phase, Winding, occurs when the function is calling itself and pushing values on the Stack. The second phase, Unwinding, occurs when the function is popping values from the stack.

Workshop

Before we look at backtracking, you should clearly understand how recursion works. We strongly recommend that you answer the following questions before you proceed to the next chapter.

Q1 : Look at the following two examples, and try to guess the answer to the question before clicking on the 'Tell me the answer' button.

Example 1 function Summation(N){ alert(N); if(N==1) return 1 else return N+Summation(N-1) }

Example 2 function Summation(N){ if(N==1) return 1 else return N+Summation(N-1) alert(N); }

The Question : For each function, if the function is passed the value 5, how many times will you see the alert box, and in what order will you see it's values?

Q2 : The Fibonacci sequence is defined as 1,1,2,3,5,8,13..., where each number is the sum of the preceding two numbers, except the first and second numbers in this sequence which are defined as having the value 1. Deduce an inductive definition of this function and use it to write a function Fibo(N), which takes a single integer parameter and returns the Nth Fibonacci number. For example, Fibo(6) should return 8.

Write the JavaScript code in the box below. The function stub has already been entered for you, do not alter it. Click on the 'Check my code' button when you are done. If you see the standard JavaScript Error alert, it means you have syntax errors in your code.

function Fibo(N){ }

Next : Decision Trees