| Inside Technique : Backtrack Recursion and the Mysterious Maze BacktrackingChapter 1 : RecursionBacktracking 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 RecursionThe 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 StackThe 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 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
WorkshopBefore 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.
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.
Page 1:Backtrack Recursion and the Mysterious Maze © 1997-2000 InsideDHTML.com, LLC. All rights reserved. |