Memoized recursive fibonacci in Python

A slow literal implementation of fibonacci function in Python is like the below:

def fib(n):
    return n if n < 2 else fib(n-2) + fib(n-1)

This is slow but you can make it faster with memoize technique, reducing the order.

__fib_cache = {}
def fib(n):
    if n in __fib_cache:
        return __fib_cache[n]
    else:
        __fib_cache[n] = n if n < 2 else fib(n-2) + fib(n-1)
        return __fib_cache[n]

This is fast, but obviously dirty. Fortunately Python has decorator feature that gives you much better way of writing.

def memoize(f):
    cache = {}
    def decorated_function(*args):
        if args in cache:
            return cache[args]
        else:
            cache[args] = f(*args)
            return cache[args]
    return decorated_function

@memoize
def fib(n):
    return n if n < 2 else fib(n-2) + fib(n-1)

The @memoize decorator is not only for this fib() function but also for general purpose. I referred this page. This is succinct and clean.

But I felt that the definition of memoize(), particularly decorated_function(), was too long. If the else clause consists of single return statement, you may re-write decorated_function() in 1 line.

Takeshi Abe taught me how to make the two lines into one single line.

cache[args] = f(*args)
return cache[args]

is equivalent to

cache.update({args: f(*args)}) or cache[args]

So let here is the final version of fib with memoize:

def memoize(f):
    cache = {}
    return lambda *args: cache[args] if args in cache else cache.update({args: f(*args)}) or cache[args]

@memoize
def fib(n):
    return n if n < 2 else fib(n-2) + fib(n-1)

It's fast, short, succinct, and cool.

Footnote

This approach may be against the Python golden way.

• http://twitter.com/fixedpoint_jp/status/2622882236600320
• http://twitter.com/kana1/status/2611298382643200
• http://twitter.com/kana1/status/2620769314013184
• http://twitter.com/kana1/status/2622096563769344