What would be the best answer for this Fibonacci excercise in Python?

Question

What's the best answer for this Fibonacci exercise in Python?

http://www.scipy-lectures.org/intro/language/functions.html#exercises

Exercise: Fibonacci sequence

Write a function that displays the n first terms of the Fibonacci sequence, defined by:

• u₀ = 1; u₁ = 1

• u_(n+2) = u_(n+1) + u_n

If this were simply asking a Fibonacci code, I would write like this:

def fibo_R(n):
    if n == 1 or n == 2:
        return 1
    return fibo_R(n-1) + fibo_R(n-2)
print(fibo_R(6))

... However, in this exercise, the initial conditions are both 1 and 1, and the calculation is going towards the positive direction (+). I don't know how to set the end condition. I've searched for an answer, but I couldn't find any. How would you answer this?

Answer 1

Note that u_(n+2) = u_(n+1) + u_n is equivalent to u_n = u_(n-1) + u_(n-2), i.e. your previous code will still apply. Fibonacci numbers are by definition defined in terms of their predecessors, no matter how you phrase the problem.

A good approach to solve this is to define a generator which produces the elements of the Fibonacci sequence on demand:

def fibonacci():
    i = 1
    j = 1

    while True:
        yield i
        x = i + j
        i = j
        j = x

You can then take the first N items of the generator via e.g. itertools.islice, or you use enumerate to keep track of how many numbers you saw:

for i, x in enumerate(fibonacci()):
  if i > n:
    break
  print x

Having a generator means that you can use the same code for solving many different problems (and quite efficiently though), such as:

• getting the n'th fibonacci number
• getting the first n fibonacci numbers
• getting all fibonacci numbers satisfying some predicate (e.g. all fibonacci numbers lower than 100)

Answer 2

The best way to calculate a fibonacci sequence is by simply starting at the beginning and looping until you have calculated the n-th number. Recursion produces way too many method calls since you are calculating the same numbers over and over again.

This function calculates the first n fibonacci numbers, stores them in a list and then prints them out:

def fibonacci(n):
    array = [1]
    a = 1
    b = 1
    if n == 1:
        print array
    for i in range(n-1):
        fib = a + b
        a = b
        b = fib
        array.append(fib)
    print array

Answer 3

If you want a super memory-efficient solution, use a generator that only produces the next number on demand:

def fib_generator():
  e1, e2 = 0, 1
  while True:
    e1,e2 = e2, e1+e2
    yield e1

f = fib_generator()
print(next(f))
print(next(f))
print(next(f))
## dump the rest with a for-loop
for i in range(3, 50):
  print(next(f))

The recursive solution is the most elegant, but it is slow. Keiwan's loop is the fastest for a large number of elements.

Yes, definitely no globals as correctly observed by DSM. Thanks!

Answer 4

An alternative recursive just to show that things can be done in slightly different ways:

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