def fibonacci_naive(n):
    if n <= 1:
        return n
    return fibonacci_naive(n-1) + fibonacci_naive(n-2)

def fibonacci_memo(n, memo={}):
    if n in memo:
        return memo[n]    # Cache hit!
    if n <= 1:
        memo[n] = n
        return n
    memo[n] = fibonacci_memo(n-1, memo) + fibonacci_memo(n-2, memo)
    return memo[n]

# fib(5) = 5
# Naive calls: 15 vs Memoized: 6

function fibNaive(n) {
    if (n <= 1) return n;
    return fibNaive(n-1) + fibNaive(n-2);
}

function fibMemo(n, memo = {}) {
    if (n in memo) return memo[n];
    if (n <= 1) { memo[n] = n; return n; }
    memo[n] = fibMemo(n-1, memo) + fibMemo(n-2, memo);
    return memo[n];
}
// fib(5) = 5