Efficient calculation of Fibonacci series

Question

I'm working on a Project Euler problem: the one about the sum of the even Fibonacci numbers.

My code:

def Fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return Fibonacci(n-1) + Fibonacci(n-2)

list1 = [x for x in range(39)]
list2 = [i for i in list1 if Fibonacci(i) % 2 == 0]

The problem's solution can be easily found by printing sum(list2). However, it is taking a lot of time to come up with the list2 I'm guessing. Is there any way to make this faster? Or is it okay even this way...

(the problem: By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.)

Answer 1

Yes. The primitive recursive solution takes a lot of time. The reason for this is that for each number calculated, it needs to calculate all the previous numbers more than once. Take a look at the following image.

It represents calculating Fibonacci(5) with your function. As you can see, it computes the value of Fibonacci(2) three times, and the value of Fibonacci(1) five times. That just gets worse and worse the higher the number you want to compute.

What makes it even worse is that with each fibonacci number you calculate in your list, you don't use the previous numbers you have knowledge of to speed up the computation – you compute each number "from scratch."

There are a few options to make this faster:

---

1. Create a list "from the bottom up"

The easiest way is to just create a list of fibonacci numbers up to the number you want. If you do that, you build "from the bottom up" or so to speak, and you can reuse previous numbers to create the next one. If you have a list of the fibonacci numbers [0, 1, 1, 2, 3], you can use the last two numbers in that list to create the next number.

This approach would look something like this:

>>> def fib_to(n):
...     fibs = [0, 1]
...     for i in range(2, n+1):
...         fibs.append(fibs[-1] + fibs[-2])
...     return fibs
...

Then you can get the first 20 fibonacci numbers by doing

>>> fib_to(20)
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765]

Or you can get the 17th fibonacci number from a list of the first 40 by doing

>>> fib_to(40)[17]
1597

---

2. Memoization (relatively advanced technique)

Another alternative to make it faster exists, but it is a little more complicated as well. Since your problem is that you re-compute values you have already computed, you can instead choose to save the values you have already computed in a dict, and try to get them from that before you recompute them. This is called memoization. It may look something like this:

>>> def fib(n, computed = {0: 0, 1: 1}):
...     if n not in computed:
...         computed[n] = fib(n-1, computed) + fib(n-2, computed)
...     return computed[n]

This allows you to compute big fibonacci numbers in a breeze:

>>> fib(400)
176023680645013966468226945392411250770384383304492191886725992896575345044216019675

This is in fact such a common technique that Python 3 includes a decorator to do this for you. I present to you, automatic memoization!

import functools

@functools.lru_cache(None)
def fib(n):
    if n < 2:
        return n
    return fib(n-1) + fib(n-2)

This does pretty much the same thing as the previous function, but with all the computed stuff handled by the lru_cache decorator.

---

3. Just count up (a naïve iterative solution)

A third method, as suggested by Mitch, is to just count up without saving the intermediary values in a list. You could imagine doing

>>> def fib(n):
...     a, b = 0, 1
...     for _ in range(n):
...         a, b = b, a+b
...     return a

---

I don't recommend these last two methods if your goal is to create a list of fibonacci numbers. fib_to(100) is going to be a lot faster than [fib(n) for n in range(101)] because with the latter, you still get the problem of computing each number in the list from scratch.