Série de Fibonacci

# Determinação dos primeiros k termos da série de Fibonacci, usando uma função recursiva:
# f(0) = f(1) = 1; f(n) = f(n - 1) + f(n - 2) para n = 2, 3, ...

def def_fib_rec(the_n):
    """ slow algorithm """
    assert the_n >= 0

    if the_n < 2:
        return the_n

    return def_fib_rec(the_n-2) + def_fib_rec(the_n-1)



def def_bits(the_n):
    """ represent an integer as an array of binary digits  """
    the_bits = []

    while the_n > 0:
        the_n, the_bit = divmod(the_n, 2)
        the_bits.append(the_bit)

    the_bits.reverse()

    return the_bits


def def_fib_fast(the_n):
    """ good algorithm """
    assert the_n >= 0

    the_a, the_b, the_c = 1, 0, 1

    for the_bit in def_bits(the_n):
        if the_bit:
            the_a, the_b = (the_a+the_c)*the_b, the_b*the_b + the_c*the_c
        else:
            the_a, the_b = the_a*the_a + the_b*the_b, (the_a+the_c)*the_b

        the_c = the_a + the_b

    return the_b