A Python example of dynamic programming for the recursive Fibonacci sequence algorithm

main.py

#!/usr/bin/env python3


from enum import auto, Enum, unique


def fib_recursive(n, calculated_results=None):
    if calculated_results is not None and n in calculated_results:
        result = calculated_results[n]
    else:
        if n < 2:
            result = n
        else:
            n_mins_1_result = fib_recursive(n - 1, calculated_results)
            n_mins_2_result = fib_recursive(n - 2, calculated_results)

            result = n_mins_1_result + n_mins_2_result

        if calculated_results is not None:
            calculated_results[n] = result

    return result


def fib_iterative(n):
    if n < 2:
        return n

    n_minus_1 = 1
    n_minus_2 = 1
    result = 1

    for _ in range(2, n):
        n_minus_2 = n_minus_1
        n_minus_1 = result
        result = n_minus_1 + n_minus_2

    return result


@unique
class FibonacciComputationTypes(Enum):
    recursive = auto()
    recursive_dynamic = auto()
    iterative = auto()


def fib_driver(n, fibonacci_computation_type):
    if fibonacci_computation_type == FibonacciComputationTypes.recursive:
        result = fib_recursive(n)
    elif fibonacci_computation_type == FibonacciComputationTypes.recursive_dynamic:
        result = fib_recursive(n, {})
    elif fibonacci_computation_type == FibonacciComputationTypes.iterative:
        result = fib_iterative(n)
    else:
        raise Exception("Oops")

    return result


def main():
    for i in range(0, 35):
        print(f"fib({i}) = {fib_driver(i, FibonacciComputationTypes.iterative)}")


if __name__ == "__main__":
    main()