0

Hi I'm fairly new to python and trying to create a Fibonacci calculator function that prints all values up to a given number, if the number entered is not in the sequence then it adds the next Fibonacci number to the list. For example, if 10 is entered it should return [0, 1, 1, 2, 3, 5, 8, 13]. The function has to be recursive. Here is my current code:

def fibonacci(n):
    n = int(n)
    # The nested sub_fib function computes the Fibonacci sequence

    def sub_fib(n):
        if n < 2:
            return n
        else:
            return (sub_fib(n-1) + sub_fib(n-2))

    #This aspect of the main fib function applies the condition if the number
    # input is not in the sequence then it returns the next value up

    fib_seq= [sub_fib(i) for i in range(0,n) if sub_fib(i)<=n]
    if fib_seq[-1] < n:
        fib_seq.append(fib_seq[-1] + fib_seq[-2])
        return fib_seq
    else:
        return fib_seq
print(fibonacci(input("Input a number to print sequence up to: ")))

I've managed to get it to work but it is incredibly slow (I assume due to the recursion) is there anyway I can speed it up without massively changing the program?

Improve this question
7
  • That's because it is recursive and does not use memoization... Is recursion realy a requirement? Commented Mar 2, 2017 at 10:32
  • 6
    Possible duplicate of How to write the Fibonacci Sequence in Python Commented Mar 2, 2017 at 10:34
  • @WillemVanOnsem, no need for memoization - enough to re-define sub_fib as generator. Commented Mar 2, 2017 at 10:42
  • 1
    @volcano: in that case making it recursive is however very useless. Commented Mar 2, 2017 at 10:43
  • @WillemVanOnsem, oops, missed that point Commented Mar 2, 2017 at 10:45

3 Answers 3

Reset to default
2

The two main reasons why your program is slow:

  • you calculate each Fibonacci number separately, you do not reuse the effort you have invested in finding the previous number;
  • you calculate the first n Fibonacci numbers, but from the moment the condition fails, you can stop.

You can change the program to still be recursive, but reuse the work to compute the previous number, and stop from the moment you have constructed the list.

You simply have to use the following function:

def fibon(a,b,n,result):
    c = a+b
    result.append(c)
    if c < n:
        fibon(b,c,n,result)
    return result

and we initialize it with: fibon(0,1,n,[]). In each iteration, it will calculate the next Fibonacci number c = a+b and append it to the result. In case that number is still smaller than c < n then we need to calculate the next number and thus perform the recursive call.

def fibonacci(n):
    n = int(n)

    def fibon(a,b,n,result):
        c = a+b
        result.append(c)
        if c < n:
            fibon(b,c,n,result)
        return result

    return fibon(0,1,n,[])

print(fibonacci(input("Input a number to print sequence up to: ")))
Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

So you initialise it with fibon(0,1,n,[]) and then each call the values a,b and thus c are updated by the previous values until c is not less than n? It works perfectly, I just want to make sure I understand it before I continue.
@Boogieboots: indeed.
0

This uses recursion but much faster than naive recursive implementations

def fib(n):
    if n == 1:
        return [1]
    elif n == 2:
        return [1, 1]
    else:
        sub = fib(n - 1)
        return sub + [sub[-1] + sub[-2]]
Improve this answer

Comments

0

Here are some examples of how you can improve the speed:

"""
Performance calculation for recursion, memoization, tabulation and generator

fib took: 27.052446
mem_fib took: 0.000134
tabular_fib took: 0.000175
yield_fib took: 0.000033
"""
from timeit import timeit


LOOKUP_SIZE = 100
number = 30
lookup = [None] * LOOKUP_SIZE


def fib(n):
    return 1 if n <= 2 else fib(n - 1) + fib(n - 2)


def mem_fib(n):
    """Using memoization."""
    if n <= 2:
        return 1
    if lookup[n] is None:
        lookup[n] = mem_fib(n - 1) + mem_fib(n - 2)

    return lookup[n]


def tabular_fib(n):
    """Using Tabulation."""
    results = [1, 1]
    for i in range(2, n):
        results.append(results[i - 1] + results[i - 2])
    return results[-1]


def yield_fib(n):
    """Using generator."""
    a = b = 1
    yield a
    yield b
    while n > 2:
        n -= 1
        a, b = b, a + b
        yield b


for f in [fib, mem_fib, tabular_fib, yield_fib]:
    t = timeit(stmt=f"f({number})", number=10, globals=globals())
    print(f"{f.__name__} took: {t:.6f}")
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.