Title: Use three important techniques to calculate Fibonacci numbers in Python

[Fibonacci numbers calculated by recursion, dynamic programming, and bottom-up programming]

The Fibonacci sequence is recursively defined like this:

Fibonacci(0) = 0 Fibonacci(1) = 1 Fibonacci(n) = Fibonacci(n - 1) + Fibonacci(n - 2) for n > 1

For example, here are the first 13 values in the sequence.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

You probably won't need the sequence itself very often, but it provides a useful exercise in three important programming techniques: recursion, dynamic programming, and bottom-up programming.

Recursion

The Fibonacci sequence is defined recursively so it makes sense to calculate it recursively. The following code uses recursion (where the code calls itself) to calculate Fibonacci numbers.

def fibonacci_recursive(n): '''Use recursion to calculate Fibonacci(n).''' if n <= 1: # Return 0 and 1. return n # Recursively calculate Fibonacci(n - 1) and Fibonacci(n - 2). return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)

If the input value n is less than or equal to 1, the function simply returns n.

For larger values, the function calls itself recursively to calculate Fibonacci(n - 1) and Fibonacci(n - 2), adds those values, and returns the sum.

Note that this code isn't bulletproof. It really should check that the input n is an integer greater than or equal to 0, but I want to keep the code relatively simple.

This method works and fits the definition of the sequence nicely, but it has a huge problem. To calculate Fibonacci(n), the code first calculates Fibonacci(n - 1) and Fibonacci(n - 2). To calculate Fibonacci(n - 1), the function calculates Fibonacci(n - 2) and Fibonacci(n - 3). That means it's calculating Fibonacci(n - 2) twice.

When you calculate Fibonacci(n - 2) twice, you'll need to calculate Fibonacci(n - 3) even more times.

If you look through all of the calculations, it turns out that the recursive function it recalculating the same values an enormous number of times. It calculates Fibonacci(0) and Fibonacci(1) a ginormous number of times. Those calculations are easy, but they add up.

For example, to calculate Fibonacci(35), the function calls itself a whopping 29,860,702 times! That means the recursive method only works for relatively small values of n.

If you look at the picture at the top of the post, you'll see that the recursive function took 1.72 seconds to calculate Fibonacci(35). That's not too bad, but you don't need to make n much bigger before this method become impractical.

Dynamic Programming

Dynamic programming addresses the "calculating the same value too many times" problem by storing intermediate values so they can be reused as needed. The program is sort of leaving itself memos holding pieces of data so this is sometimes called "memoization."

In this example, we need to store Fibonacci values that we might need later. Here's one way to do that.

def fibonacci_dynamic(n, values=None): '''Use dynamic programming to calculate Fibonacci(n).''' # If we have no saved values, make a new dictionary. if values is None: values = {} # If the value is not in the dictionary, find it and put it there. if n not in values: if n <= 1: values[n] = n else: values[n] = \ fibonacci_dynamic(n - 1, values) + \ fibonacci_dynamic(n - 2, values) # Return the value in the dictionary. return values[n]

This function takes an optional values parameter to hold previously calculated values. If that parameter is missing, the function creates a new values dictionary.

Next, the code checks whether n is in the dictionary. If the value isn't there, the code calculates it and adds it to the dictionary.

To calculate the value, the code checks whether n <= 1. If that's true, the code saves value[n] = n.

If n is greater than 1, the function recursively calls itself to calculate Fibonacci(n - 1) and Fibonacci(n - 1), adds them, and saves the sum in the values dictionary.

After the if n not in values section finishes, we know that the desired value is in the values dictionary so the function gets that value and returns it.

Like the previous function, this one is recursive, so you may wonder if we really accomplished much. The difference is that this version memoizes Fibonacci numbers so it doesn't need to calculate them again. When you initially call the function, the recursion runs all the way to Fibonacci(0), but after that it never needs to calculate any of those values again. The previous function spends a huge amount of time crawling up and down a call tree but this version only climbs through it from bottom to top once.

If you look at the picture at the top of the post, you can see that this function took only 0.000780 seconds to calculate Fibonacci(2000), which is a 413 digit number.

Bottom-Up Programming

Dynamic programming avoids recalculating the same values many times, but it has some drawbacks. First, there's extra overhead managing the memos stored in the dictionary. That slows the function down, but it can still calculate Fibonacci(2000) in less than a millisecond, so that's not too shabby.

A worse problem is that this method requires deep recursion. To calculate Fibonacci(n), the function calls itself to calculate Fibonacci(n - 1), which calls itself to calculate Fibonacci(n - 2), and so on all the way down to calculating Fibonacci(0) so the call stack is n levels deep. Python has a recursion limit, which is typically 1,000, so for large inputs the function will crash. I have my recursion limit cranked up to 3,000, but that still limits the calculation.

The solution is to reconsider how we construct the Fibonacci numbers. The previous functions use a top-down approach where they break a larger value (Fibonacci(n)) into smaller values (Fibonacci(n - 1) and Fibonacci(n - 2)).

An alternative is to think bottom-up. Here you take two smaller values and add them to get the next larger value. Here's a function based on that idea.

def fibonacci_bottom_up(n): '''Use a bottom-up approach to calculate Fibonacci(n).''' if n <= 1: # Return 0 and 1. return n # Calculate larger values. fib_i_minus_2 = 0 fib_i_minus_1 = 1 for i in range(2, n+1): new_value = fib_i_minus_1 + fib_i_minus_2 fib_i_minus_2 = fib_i_minus_1 fib_i_minus_1 = new_value return new_value

This function first returns n if n is 0 or 1.

Next, the code sets variables fib_i_minus_2 to Fibonacci(0) and fib_i_minus_1 to Fibonacci(1). It then enters a loop where it uses those two values to calculate the next value and saves it in variable new_value. The code updates fib_i_minus_2 and fib_i_minus_1 and continues the loop until new_value holds Fibonacci(n), when it returns that value.

This version of the function calculates the same 413 digit value as the dynamic programming version but in less than 1/5th as much time. (The exact times will vary, particularly because they're so small.)

More importantly, this version doesn't use recursion so it won't be caught by the recursion limit. This function can calculate Fibonacci numbers as big as you like if you're willing to wait long enough. For example, I was able to calculate Fibonacci(1,000,000) in about 7.8 seconds. The result has 208,986 digits so it's too big to easily display, but you can calculate it if you want.

Conclusion

Some numbers (like Fibonacci numbers) can be defined in a naturally recursive way. In that case, it makes sense to calculate them with a recursive function.

If a function, recursive or not, recalculates the same values many times, you can probably save time by using dynamic programming. Memoize the values so you don't need to calculate any one value more than once.

Sometimes you can do even better if you rethink the function's definition and use a bottom-up approach to calculate larger values from smaller ones. Then you may be able to eliminate recursion and recalculated values completely.

Download the example to experiment with it and to see additional details.