Tricks of the Windows Game Programming Gurus:Algorithms, Data Structures, Memory Management, and Multithreading

All ITKnowledge Source Code Search Tips Advanced Search |

| Tricks of the Windows Game Programming Gurus by Andre LaMothe Sams, Macmillan Computer Publishing ISBN: 0672313618 Pub Date: 09/27/99

Search this book:

Previous | Table of Contents | Next

### Recursion

The next subject I want to talk about is recursion—did you just get a stomach ache? This may or may not be familiar to you. Recursion is simply a technique of solving a problem by induction—sorta. The basis of recursion is that many problems can be broken down into simpler problems of the same form, until at some point you can actually solve the problem. Then you assemble the large problem by combining the smaller problems. Sounds good, huh?

In computer programming, we usually use recursive algorithms for searching, sorting, and some mathematical operations. The premise is simple: You write a function that has the potential to call itself to solve the problem. Sound weird? Well, the key is that when a function calls itself, a new set of local variables are created on the stack, so it’s really like another function is being called. The only things you have to worry about are that the function doesn’t overflow the stack and that there is a terminal case at which the function terminates, whereby it can “unwind” the stack via multiple `return()`s. Let’s jump into it with a standard example: the computation of a factorial.

The factorial of a number written as n! (“n bang”) has the following meaning:

    n! = n*(n-1)*(n-2)*(n-3)*…(2)*(1)

And `0! = 1! = 1`,

Thus, `5!` is `5*4*3*2*1`.

Let’s code this the normal way:

    // assume integers

    int Factorial(int n)

    {

    int sum = 1; // hold result

    // accumulate product

    while(n > 1)

         {

         sum*=n;

         // decrement n

         n--;

         } // end while

    // return the result

    return(sum);

    } // end Factorial

Looks pretty basic. If you send in a 0 or 1, you get 1. If you send it a 3, the following sequence occurs:

    sum = sum * 3 = 1 * 3 = 3

    sum = sum * 2 = 3 * 2 = 6

    sum = sum * 1 = 6 * 1 = 6

Which is correct because `3! = 3*2*1`.

Now here’s the recursive version:

    int Factorial_Rec(int n)

    {

    // test for terminal cases

    if (n==0 [vbar][vbar] n==1) return(1);

    else

       return(n*Factorial_Rec(n-1));

    } // end Factorial_Rec

Tell me that isn’t cool, my little leprechaun! So let’s see what happens here when `n` is equal to 0 or 1. In these cases, the first `if` statement is `TRUE`, 1 is returned, and the function exits. But the cool stuff happens when `n` > 1. In this case, the `else` executes and the value returned is `n` times the function itself called with (n-1). This is recursion.

The state of the current function’s variables remains on the stack, and the call is made to the function again as if it were another function with a new working set of variables. The code of the first `return` statement can’t be completed until another call is made, and that `return` can’t be completed until that call is made, and so on, until the terminal case is hit.

With that in mind, let’s take a look at the `n = 3` case with actual numbers replacing the variable `n` each iteration:

  1. Initial Call to `Factorial_Rec(3)`

  The function falls to the `return` statement:

           return(3*Factorial_Rec(2));

  2. Second call to `Factorial_Rec(2)`

  The function again falls to the `return` statement:

           return(2*Factorial_Rec(1));

  3. Third call to `Factorial_Rec(1)`

  This time the terminal case is true and a 1 is returned:

           return(1);

Now for the magic. The 1 is returned to the second call of `Factorial_Rec()` that looked like this:

    return(2*Factorial_Rec(1));

This resolves to

    return(2*1);

This then returns to the first call of `Factorial_Rec()` that looked like this:

    return(3*Factorial_Rec(2));

This resolves to

    return(3*2);

And presto, the function can finally return with 6—which is indeed 3! That’s recursion. Now, you might ask which method is better—recursion or non-recursion? Obviously, the straightforward method is faster because there aren’t any function calls or stack manipulation, but the recursive way is more elegant and better reflects the problem. This is the reason why we use recursion. Some algorithms are recursive in nature, trying to write non-recursive algorithms is tedious, and in the end they become recursive simulations that use stacks themselves! So use recursion if it’s appropriate and simplifies the problem. Otherwise, use straight linear code.

For an example of recursion, take a look at `DEMO11_2.CPP[vbar]EXE`. It implements the factorial algorithm. Note how quickly factorial can overflow! See if the computer can beat your calculator’s max factorial. Most calculators can compute up to 69! No lie.

Math For you math people, try implementing a recursive Fibonacci algorithm. Remember, the `n`th Fibonacci number fn = fn-1 + fn-2, f0=0, and f1=1. Hence, f2= f1 + f0 = 1 + 0 = 1, and f3= f2 + f1 = 1 + 1 = 2. Therefore, the Fibonacci sequence looks like 0, 1, 1, 2, 3, 5, 8, 13… Count the number of seeds in each of the consecutive rings of a sunflower plant, and they will be the Fibonacci sequence!

Previous | Table of Contents | Next

Copyright © Macmillan Computer Publishing, Inc.

Products | Contact Us | About Us | Privacy | Ad Info | Home
Use of this site is subject to certain Terms & Conditions, Copyright © 1996-2000 EarthWeb Inc. All rights reserved. Reproduction in whole or in part in any form or medium without express written permission of EarthWeb is prohibited. Read EarthWeb's privacy statement.