fibonacci.py

# Fibonacci tool
# This script only works with Python3!

import time


def getFibonacciIterative(n: int) -> int:
    """
    Calculate the fibonacci number at position n iteratively
    """

    a = 0
    b = 1

    for _ in range(n):
        a, b = b, a + b

    return a


def getFibonacciRecursive(n: int) -> int:
    """
    Calculate the fibonacci number at position n recursively
    """

    a = 0
    b = 1

    def step(n: int) -> int:
        nonlocal a, b
        if n <= 0:
            return a
        a, b = b, a + b
        return step(n - 1)

    return step(n)


def getFibonacciDynamic(n: int, fib: list) -> int:
    """
    Calculate the fibonacci number at position n using dynamic programming to improve runtime
    """

    if n == 0 or n == 1:
        return n
    if fib[n] != -1:
        return fib[n]
    fib[n] = getFibonacciDynamic(n - 1, fib) + getFibonacciDynamic(n - 2, fib)
    return fib[n]


def main():
    n = int(input())
    fib = [-1] * n
    getFibonacciDynamic(n, fib)


def compareFibonacciCalculators(n: int) -> None:
    """
    Interactively compare both fibonacci generators
    """

    startI = time.clock()
    resultI = getFibonacciIterative(n)
    endI = time.clock()

    startR = time.clock()
    resultR = getFibonacciRecursive(n)
    endR = time.clock()

    s = "{} calculting {} => {} in {} seconds"
    print(s.format("Iteratively", n, resultI, endI - startI))
    print(s.format("Recursively", n, resultR, endR - startR))