Features
Resources
Community
Members
Upcoming Events
Unite 2010
11/10 - 11/12 @ Montréal, Canada

GDC China
12/5 - 12/7 @ Shanghai, China

Asia Game Show 2010
12/24 - 12/27

GDC 2011
2/28 - 3/4 @ San Francisco, CA

More events...
Quick Stats
114 people currently visiting GDNet.
2406 articles in the reference section.

Help us fight cancer!
Join SETI Team GDNet!

In this column, we will discuss memoization – a technique to speed up recursive computations.

# Recursion

In mathematics and computer science, recursion is a way of specifying something (usually a mathematical object or part of a computer program) by reference to itself. More precisely (and to dispel the appearance of circularity in the definition), "complicated" instances are defined in terms of "simpler" instances, and the "simplest" instances are given explicitly.

One interesting "application" of recursion is the definition of the set of natural numbers. We can define a natural number recursively as follows:

• 0 is natural
• If n is natural, then n + 1 is also natural

So, 0 is natural by definition. 1 is natural, because 0 is natural and 1 = 0 + 1. 2 is natural because 2 = 1 + 1 and 1 is natural, and so on.

# Fibonacci numbers

A canonical example of recursion is the computation of Fibonacci numbers:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946 ...

This sequence can be defined recursively as follows (F(n) is the nth Fibonacci number):

• if n = 0, F(n)= 0
• if n = 1, F(n) = 1
• otherwise, F(n) = F(n - 1) + F(n - 2)

You can easily follow this definition and generate some Fibonacci numbers for yourself - you will get precisely the sequence given above.

How would we generate this sequence in code? It's quite simple - recursive definitions are easily reflected in recursive function calls. Here is the C++ code that returns any Fibonacci number (constrained by execution-time and limitations of the C++ long type):

```long fib_rec( long index )
{
if (index < 2)
return index;
else
return fib_rec(index - 1) + fib_rec(index - 2);
}
```

Note how gracefully the mathematical definition is translated to the code of fib_rec. This is the beauty and elegance of recursion. Unfortunately, everything has its price. While often being the most natural way to express algorithms, recursion can suffer from performance problems.

For example, finding the 40th Fibonacci number (which is, by the way, 102,334,155) using this routine takes about 4 seconds on my machine. The 42nd number (267,914,296) takes 11 seconds to compute, and the time grows very quickly (the 45th, which is 1,134,903,170, takes 47 seconds, etc.)

One reason for this is the cost of function calls (of which there are many in the recursive solution). When a function is called, there is always a certain amount of overhead. For small functions, this overhead can be comparable to the time required to execute the function itself. This results in a performance hit.

However, this is not the main reason for recursion being slow for the computation of Fibonacci numbers. The principal cause, in this case, is the vast amount of repetition involved. To demonstrate this, let's try to trace a sample execution of the recursive computation fib_rec, taking a call with index set to 5 as an example:

```fib_rec(5)
|
|---fib_rec(4)
|   |
|   |---fib_rec(3)
|   |   |
|   |   |---fib_rec(2)
|   |   |   |
|   |   |   |---fib_rec(1)
|   |   |   |---fib_rec(0)
|   |   |
|   |   |---fib_rec(1)
|   |
|   |---fib_rec(2)
|       |
|       |---fib_rec(1)
|       |---fib_rec(0)
|
|---fib_rec(3)
|
|   fib_rec(2)
|   |
|   |---fib_rec(1)
|   |---fib_rec(0)
|
|---fib_rec(1)
```

When fib_rec(5) is called, it calls fib_rec with 4 and fib_rec with 3. Each of those makes the appropriate calls, et cetera. What you see above is the complete call tree that results from the fib_rec(5). You can generate it yourself by inserting a tracing printout in the beginning of the function.

Now, do you notice anything funny about this call tree? It shouldn't be hard to spot the scandalous number of times the same calls are made. For instance, the call fib_rec(1) is made 5 times. The result of fib_rec(i) surely doesn't change between calls (the first Fibonacci number is, by definition, 1), so why is there a need for so much repetition? This, in fact, is the reason for the unfortunate inefficiency of recursive algorithms for many computations. So can we really write nice recursive algorithms and not be daunted by their performance problems? The answer to this question is fortunately positive!

Memoized Fibonacci

Contents
 Recursion Memoized Fibonacci Counting change