Different approaches to program the Fibonacci sequence algorithm.

fibonacci.py

# -*- coding:utf-8 -*-
# Different approaches to program the Fibonacci sequence algorithm.
#
# - Bottom-up stack recursion.
# - Top-down tail recursion.
# - Bottom-up iterative.
# - Bottom-up dynamic programming.
# - Top-down dynamic programming.
#
# For more information see:
#     http://en.wikipedia.org/wiki/Fibonacci_number
#


def fib1(x):
    """
    Bottom-up stack recursion.
    """

    if x < 1:
        return 0

    def fib1_aux(idx, trgt, m2, m1):
        if idx == trgt:
            return m1
        return fib1_aux(idx + 1, trgt, m1, m2 + m1)

    return fib1_aux(1, x, 0, 1)


def fib2(x):
    """
    Top-down tail recursion.
    """
    if x < 1:
        return 0

    if x in [1, 2]:
        return 1

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


def fib3(x):
    """
    Bottom-up iterative.
    """
    if x < 1:
        return 0

    idx = 1
    a = 0
    b = 1
    aux = -1

    while idx < x:
        aux = a
        a = b
        b = aux + b
        idx += 1

    return b


def fib4(x):
    """
    Bottom-up dynamic programming.
    """

    if x < 1:
        return 0

    lst = [0, 1]
    idx = 1

    while idx < x:
        lst.append(lst[-1] + lst[-2])
        idx += 1

    return lst[-1]


def fib5(x):
    """
    Top-down dynamic programming.
    """
    if x < 1:
        return 0

    if x not in fib5.memory:
        fib5.memory[x] = fib5(x - 1) + fib5(x - 2)
    return fib5.memory[x]

fib5.memory = {
    0: 0,
    1: 1
}


CALCULATED = (
    (0, 0),
    (1, 1),
    (2, 1),
    (3, 2),
    (4, 3),
    (5, 5),
    (6, 8),
    (7, 13),
    (8, 21),
    (9, 34),
    (10, 55),
    (25, 75025),
    (30, 832040),
)

if __name__ == '__main__':
    for func in [fib1, fib2, fib3, fib4, fib5]:
        for x, r in CALCULATED:
            c = func(x)
            print('{}({}) = {}{}'.format(
                func.__name__,
                x, c,
                '' if c == r else ' (!={})'.format(r))
            )
        print('-' * 20)