Return to Answer

Important limitation: Both of these implementations will raise a RuntimeError with recursion limit exceeded if you want to get a too big Fibonacci number right away (where too big is somewhere > 250). Here, you can, however, use what you already have and just calculate all Fibonacci numbers up to that number:

Important limitation: Both of these implementations will raise a RuntimeError with recursion limit exceeded if you want to get a too big Fibonacci number right away (where too big is already somewhere between 250 and 300). Here, you can, however, use what you already have and just calculate all Fibonacci numbers up to that number:

import functools

def memoize(func):
    cache = func.cache = {}

    @functools.wraps(func)
    def wrapper(n):
        if n not in cache:
            cache[n] = func(n)
        return cache[n]
    return wrapper


def memodict(f):
    """ Memoization decorator for a function taking a single argument """
    class MemoDict(dict):
        def __missing__(self, key):
            ret = self[key] = f(key)
            return ret
    return MemoDict().__getitem__

@memodict
def fib(n):
    if n < 1:
        raise ValueError("This Fibonacci sequence starts at the index 1")
    if fib in (1, 2):
        return 1
    return fib(n-1) + fib(n-2)

Important limitation: Both of these implementations will raise a RuntimeError with recursion limit exceeded if you want to get a too big Fibonacci number right away. Here, you can, however, use what you already have and just calculate all Fibonacci numbers up to that number:

for n in range(large_number):
    fib(n)
print fib(large_number)

import functools

def memoize(func):
    cache = func.cache = {}

    @functools.wraps(func)
    def wrapper(n):
        if n not in cache:
            cache[n] = func(n)
        return cache[n]
    return wrapper


def memodict(f):
    """ Memoization decorator for a function taking a single argument """
    class MemoDict(dict):
        def __missing__(self, key):
            ret = self[key] = f(key)
            return ret
    return MemoDict().__getitem__

@memodict
def fib(n):
    if n == 0:
        return 0
    if n in (1, 2):
        return 1
    return fib(n-1) + fib(n-2)

Important limitation: Both of these implementations will raise a RuntimeError with recursion limit exceeded if you want to get a too big Fibonacci number right away (where too big is somewhere > 250). Here, you can, however, use what you already have and just calculate all Fibonacci numbers up to that number:

for n in xrange(large_number):  # Use range in python 3.x
    fib(n)
print fib(large_number)

Both of these implementations will raise a RuntimeError with recursion limit exceeded if you want to get a too big Fibonacci number right away. Here, you can, however, use what you already have and just calculate all Fibonacci numbers up to that number:

Important limitation: Both of these implementations will raise a RuntimeError with recursion limit exceeded if you want to get a too big Fibonacci number right away. Here, you can, however, use what you already have and just calculate all Fibonacci numbers up to that number: