fibonacci program hangs after 40th term

Question

I am trying to solve this problem

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

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

Link: https://projecteuler.net/problem=2

Below is the code I have to calculate a fibonacci number:

# fibonacci series
def fib(x):
    if x==0 or x==1:
        return 1                         
    else:
        return fib(x-1) + fib(x-2)

def test_fib(n):
    for i in range (n+1):
        print 'fib of', i, ' = ' , fib(i)

test_fib(41)

However, the program hangs after 40th term. What is the problem with this code and how to solve this problem for 40th and beyond terms?

Answer 1

A naive recursive implementation of the fibonacci algorithm will get slow really fast. There's two ways you can resolve this:

a) Switch to an iterative version

def fib(x):
    if x==0 or x==1:
        return 1                         
    a = b = 1
    for _ in range(x-1):
        a, b = b, a+b
    return b

This is less elegant than the recursive solution, but has linear time complexity.

b) Use memoization:

from functools import lru_cache

@lru_cache()
def fib(x):
    if x==0 or x==1:
        return 1                         
    else:
        return fib(x-1) + fib (x-2)

This is the recursive solution, but with a "memory". It has the added benefit of being even faster than the iterative version if you have to call the function many times.

In old versions of Python (e.g. 2.7), lru_cache didn't exist yet, but you implement a cheap copy that's enough for our use:

def lru_cache():
    # second-order decorator to be a drop-in replacement
    def decorator(fn):
        cache = {}
        def wrapped(*args, **kwargs):
            if args in cache:
                return cache[args]
            val = fn(*args)
            cache[args] = val
            return val
        return wrapped
    return decorator

Answer 2

considering the terms in the Fibonacci sequence whose values do not exceed four million

The 34th term exceeds four million, so you don't need beyond the 40th term. Problem solved.

A naive recursive implementation of the fibonacci algorithm will get slow really fast. There's two ways you can resolve this:

A third approach is to use a recursive solution that isn't naive. One problem with your original is it's doubly recursive:

return fib(x-1) + fib(x-2)

Let's reduce that to a single recursion:

def fib(n, res=0, nxt=1):
    if n == 0:
        return res
    return fib(n - 1, nxt, res + nxt)

This gets you past the 40th term, bottoming out recursion-wise at the 997th. If you need to go further, consider either @L3viathan's iteration or memoization solutions which are both excellent.

Answer 3

First of all here is a working Fibonacci number generator:

a,b = 0,1
print(a,b)
for x in range(0, 100):
    a,b = b, a + b
    print(b)

Next all you have to do is this:

a,b = 0,1
print(a,b)
for x in range(0, 100):
    a,b = b, a + b
    c = 0
    if b % 2 == 0:
        c = c + b
        print(c)

The final iteration of c is your answer.

Answer 4

This will add your terms until a is bigger then 4 million:

def fibo(n):
    i = 0
    a = 1
    b = 1
    sumEven= 0
    while i<n and a < 4000000:
        print ("fib of ", i, " = ", a)
        if(a % 2==0):
            sumEven+=a
        a,b = b, b+a
        i+=1
    print("sum of even: ", sumEven)

fibo(50)