Optimize Recursion

We can easily optimize a recursion by using a cache, which loads calculated function calls during the recursion process.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


from functools import wraps

def memo(func):
    cache = dict()

    @wraps(func)
    def wrap(*args):
        if args not in cache:
            cache[args] = func(*args)
        return cache[args]
    return wrap

Some conditional branches could be merged by and operator.

1
2
3
4
5
6


@memo
def fib(n: int) -> int:
    if n in {0, 1}:
        return 1
    else:
        return fib(n-1) + fib(n-1)