fibonacci.py

"""
Implementaço de vários algoritmos Fibonacci

A lib "time" foi utilizada para marcar o tempo de
execução dos algoritmos em segundos
"""

import functools
import time


def fib_iterativa(number):
    """Fibonacci iterativa."""
    last = 0
    curr = 1
    for _ in range(0, number):
        last, curr = curr, curr + last
    return last


def fib_recursiva(number):
    """Fibonnaci recursiva."""
    if number < 2:
        return number
    return fib_recursiva(number - 1) + fib_recursiva(number - 2)


@functools.lru_cache(maxsize=None)
def fib_recursiva_com_cache(number):
    """Fibonacci recursiva com cache."""
    if number < 2:
        return number
    return fib_recursiva_com_cache(number - 1) + fib_recursiva_com_cache(
        number - 2
    )


def run_fibonacci(name, func, number=35):
    """
    Roda o algoritmo e mostra o tempo de execução dele
    """
    start_time = time.time()
    result = func(number)
    diff_time = time.time() - start_time
    print('Fibonacci', name, ':', result, ':', '%.8f' % diff_time, 'segundos')


if __name__ == "__main__":
    run_fibonacci('Iterativa', fib_iterativa)
    run_fibonacci('Recursiva', fib_recursiva)
    run_fibonacci('Recursiva com Cache', fib_recursiva_com_cache)