Recursion and Memoization

Simple Recursion

def factorial(n: int) -> int:
    if n <= 1:
        return 1
    return n * factorial(n - 1)

Memoisation with lru_cache

from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci(n: int) -> int:
    if n < 2:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

Manual Memoisation

def fibonacci_manual(n: int, memo: dict = None) -> int:
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]
    if n < 2:
        return n
    memo[n] = fibonacci_manual(n - 1, memo) + fibonacci_manual(n - 2, memo)
    return memo[n]

Compile the Wrapper

pyvorin run script.py --function fibonacci