Recursion

The first thing we have to learn to develop AI is a concept called recursion. Stated simply, recursion is the act of one function calling itself. If you have a function, such as foo , that contains another call to the foo function somewhere inside it, you have a recursive structure. Consider the following simple example script.

 function foo(){       foo(); } 

This is the most basic recursive function that can be written. It doesn't actually do anything yet, but you can see that the function foo calls itself. If you tried to call foo , your Flash movie would give you an error saying that it has exceeded 256 levels of recursion and will stop the script. Without the failsafe, the function foo would continue to call itself endlessly, creating an infinite loop.

Now that you know the basic idea behind recursion, it's time for some examples. Please note that the idea here is to give you simple examples of recursion so that you can focus on the idea of recursion. In actuality, most of these examples can and should be implemented with iterative loops . We are going to solve them recursively only for the benefit of learning recursion. After you understand basic recursion, we can use it to do more complex things that would be impossible with normal loops.

Recursion Example: Factorial

In mathematics, the factorial operator (!) denotes the multiplication of all consecutive integers up to the number given before the factorial sign. In other words, 5 factorial, written as 5!, would be equivalent to the following. (Don't confuse this mathematical operator with ActionScript's logical NOT operator.)

• 5! = 1 · 2 · 3 · 4 · 5 = 120

For factorials, 0 is a special case; 0! is defined to be 1. Also, the factorial operator is not used for negative values or any noninteger number. We'll need to account for both of these exceptions in our factorial function.

ActionScript does not contain a factorial function, so if you need one, you have to make your own. Before we solve this problem recursively, I want to show an iterative solution using loops to ensure that you understand factorials before we introduce the recursion.

 function factorial(n){       if(n<0) return NaN;       var value=1;       for(;n>1;-n) value*=n;       return value; } 

First we test to see if our argument, n , is less than 0. If it is, we return NaN to signal Not a Number (NAN). Following that is the declaration of a temp variable named value . Then we go into a loop. Notice that I've omitted the first part of the for loop; we will be using n (the argument to factorial ) for the condition of the loop. The variable n is already defined, so we don't need to initialize it. After each iteration of the loop, we multiply value by n and assign the product to value . After the loop, we return value .

Now we can test this function with a loop that calls our factorial function. This loop iterates from -2 to 10, yielding the factorials of each of those numbers .

 for(var i=-2;i<10;++i) trace(i+"! = "+factorial(i)); 

Figure 10.1 shows this script and its output. If you calculate the factorials with a calculator, you'll see the same results.

Figure 10.1: This first factorial function correctly computes factorials using loops.

Now we can build a recursive solution to this problem. We need to rewrite the factorial so that instead of using a loop, it will call itself. The principal is nearly the same, but the style with which we build the function is different. Consider the following:

 function factorial(n){       if(n<0) return NaN;  if(n==0  n==1) return 1;   return n * factorial(n-1);  } 

Study this new function closely. The first line checks for n less than 0 and returns NaN if it occurs. That's identical to the previous function. The next line tests for n being equal to 0 or 1. In both of those cases, we return 1. The final line causes the recursion. We return the product of n and the value returned by a call to factorial where we reduce the value of n by 1. You might be able to see how this is working now. The recursive factorial function calls itself with successively smaller values of n until n becomes 1. Then the functions start returning from their recursion. Figure 10.2 illustrates the levels of factorial calls that make up the recursive solution for a factorial of 4.

Figure 10.2: The factorial function is called by itself several times with lesser values of n each time. When n becomes 1, everything returns.

Now we can add the test line.

 for(var i=-2;i<10;++i) trace(i+"! = "+factorial(i)); 

You can see the output of this new recursive function in Figure 10.3. Compare this with the output in Figure 10.1 to see that they are identical.

Figure 10.3: The new recursive factorial function gives identical output to the old iterative solution.

Many people find recursion to be somewhat tricky at first. You might have an idea of how it works but not be ready to build your own recursive solution to some problem. If so, try to build a recursive solution to the Math.pow function. The next section describes the solution, but if you make an attempt on your own first, you'll ultimately get more out of the explanation.

Recursion Example: Power

The next example we're going to solve is the Math.pow function. Like the last time, I want to solve the problem iteratively first to get our heads into the problem a bit before dropping in the recursion.

We will only be solving power for positive exponents that are whole numbers. We won't handle negative exponents to keep the examples simple and to the point (recursion).

Consider the following solution:

 function power(base,exp){       if(exp<0) return NaN;       var value=1;       for(;exp>0;-exp) value*=base;       return value; } 

In this iterative solution, we have our two arguments ” base and exp ”which stand for the number that we want to raise to some power and the exponent indicating how many times to multiply the base by itself. We're checking for a base less than 0 and returning NaN in that case. Then we use a loop that decrements exp and multiplies our temp variable value by base . For each iteration, we decrement exp . Finally, we return the result.

 for(var i=0;i<10;++i) trace("2^"+i+" = "+power(2,i)); 

This test line yields output like Figure 10.4.

Figure 10.4: The power function produces correct results for a base of 2 raised to powers from 0 to 9.

Now let's take a crack at it recursively:

 function power(base,exp){       if(exp<0) return NaN;  if(exp==0) return 1;   return base*power(base,exp-1);  } 

The first change to our power function comes on the second line. We're testing to see if exp is equal to 0, and if so, we return 1. The next line causes the recursion. It returns the value of base times a call to power . In this new call to power , we're reducing the exp variable by 1. This has a similar effect to the factorial from our previous example. Now let's test to make sure it's working right. Of course, at this point, you should be fairly confident that it is.

Look at Figure 10.5, which breaks down each of the calls when computing a call to power(2,3); which, of course, gives us 2 ⁴ .

Figure 10.5: The power function is called by itself successively each time the value of the exponent ( exp ) is reduced by 1. The function starts returning when exp is 0.

Let's add the test line.

 for(var i=0;i<10;++i) trace("2^"+i+" = "+power(2,i)); 

You can see the output from this in Figure 10.6, which matches the output in Figure 10.4.

Figure 10.6: The output of our recursive power function is identical to the previous iterative solution.

Base Cases

It's time to introduce a new term regarding recursion. The concept is called a base case, and you've already seen them in our recursive examples. Inside our recursive functions, we have a series of if s and else s. These are checking values, and based on those values, we either return from our function or make another recursive call. Cases in which we return a value that is not dependent on calling the function again are called base cases . Look back at our factorial example.

A factorial has three base cases. The first is n < 0 . This base case causes a return of NaN . The second base case is n == 0 . The third and final base case is n == 1 . Both the second and third base cases return a value of 1.

Caution  

Don't be confused by the fact that the factorial's second and third base cases are in the same line ( n==0 n==1 ). They both return a value of 1, so we were able to combine them into the same if statement; technically, though, they are separate base cases.

I wanted to make this idea of a base case clear so that later when our recursive functions become complex, you'll be able to easily identify the base cases.

Now let's briefly talk about why you wouldn't want to use recursion to solve the two problems of factorial and power.

Problems with Recursion

Recursion allows us to do some interesting things, but it comes with a price. Recursion is a costly procedure in terms of running time and system resource usage. Calling a function several times takes a lot more work than iterating a loop the same number of times. For this reason, you should not use recursion unless there is no other suitable solution. A hint to help you realize when this is the case is something called tail recursion. Tail recursion is when the recursive call is the last line of the recursive function.

If you find yourself using tail recursion, the recursion is unnecessary. In other words, if you have all base cases followed by recursive calls, you could be doing the recursion with a while (or similar) loop. When possible, you should always choose to write your code in an iterative fashion rather than recursive. Only use recursion when a loop won't be enough. The following is a short example of tail recursion:

 function foo(){      /*do stuff here*/      return foo();//tail recursion and should signal you      //that you need a loop instead. } 

Notice that both the factorial and power examples used a tail recursion. Their recursive calls were the last lines in each function. If you can build a recursive function that is a tail recursion, you should build the function with no recursion at all. This should go along with the idea that factorial and power were only used to exemplify recursion; they should not be implemented with recursion in a real game or application.

When we get to the point at which our recursive functions are complex enough to be meaningful, the recursive call will come either before the base cases or somewhere in the middle of the base cases.

Now that you've seen a few examples of recursion, you should be getting a feel for how it works. It's time to introduce a new concept that is pivotal to our understanding of AI. The concept is called a tree, and it is used through recursion.