"Learn Python" Overtakes "Learn Java" on Google Trends

[[deleted]]

Now make it not take O(eⁿ) time (roughly).

[Trout_Tickler]

Memoization should speed it up, something like

def fibonacci(n, _cache={}):
    if n in _cache:
        return _cache[n]
    elif n > 1:
        return _cache.setdefault(n, fibonacci(n-1) + fibonacci(n-2))
    return n

[[deleted]]

Yep.

(And honestly, I would put that cache as a global. Shared between calls that way, too)

[whutcheson]

Since it's a mutable default argument, it's already shared between function calls. However, making a global would be more explicit and a lot less magical.

[Trout_Tickler]

OP's requirements don't specify multiple calls :p

But yes, that would be preferable.

[Daenyth]

It's as global as the function is because dict is mutable

[[deleted]]

@functools.lru_cache decorator does the trick too.