CODEWITHSUNDEEP
pythonrecursionfibonacci
Latika Agarwal
Latika Agarwal

Reputation: 969

fibonacci program hangs after 40th term

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?

Upvotes: 1

Views: 888

Answers (4)

cdlane
cdlane

Reputation: 41872

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.

Upvotes: 1

Patrick Artner
Patrick Artner

Reputation: 51643

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)

Upvotes: 0

3141
3141

Reputation: 409

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.

Upvotes: 0

L3viathan
L3viathan

Reputation: 27283

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

Upvotes: 4

Related Questions