我应该先回答第一部分:什么是记忆?

这只是一种用记忆换取时间的方法。想想乘法表。

在Python中使用可变对象作为默认值通常被认为是不好的。但如果明智地使用它，它实际上可以用于实现记忆。

下面是一个摘自http://docs.python.org/2/faq/design.html#why-are-default-values-shared-between-objects的例子

在函数定义中使用可变dict，中间计算结果可以被缓存(例如，在计算阶乘(9)后计算阶乘(10)时，我们可以重用所有中间结果)

def factorial(n, _cache={1:1}):    
    try:            
        return _cache[n]           
    except IndexError:
        _cache[n] = factorial(n-1)*n
        return _cache[n]

记忆是将函数转换为数据结构的过程。通常，人们希望增量地、惰性地进行转换(根据给定的域元素——或“键”的要求)。在惰性函数语言中，这种惰性转换可以自动发生，因此可以在没有(显式)副作用的情况下实现内存化。

只是想对已经提供的答案进行补充，Python装饰器库有一些简单但有用的实现，也可以记住“不可哈希类型”，不像functools.lru_cache。

functools。缓存装饰:

Python 3.9发布了一个新函数functools.cache。它在内存中缓存带有一组特定参数的函数调用的结果，这就是内存化。它很容易使用:

import functools
import time

@functools.cache
def calculate_double(num):
    time.sleep(1) # sleep for 1 second to simulate a slow calculation
    return num * 2

第一次调用caculate_double(5)时，它将花费一秒钟并返回10。第二次使用相同的参数calculate_double(5)调用该函数时，它将立即返回10。

添加缓存装饰器可以确保如果函数最近为某个特定值被调用，它将不会重新计算该值，而是使用先前缓存的结果。在这种情况下，它可以极大地提高速度，同时代码不会因为缓存的细节而变得混乱。

(编辑:前面的示例使用递归计算了斐波那契数，但我修改了示例以防止混淆，因此出现了旧的注释。)

functools。lru_cache装饰:

如果您需要支持旧版本的Python，请使用functools。lru_cache适用于Python 3.2+。默认情况下，它只缓存最近使用的128个调用，但你可以将maxsize设置为None来指示缓存永远不会过期:

@functools.lru_cache(maxsize=None)
def calculate_double(num):
    # etc

记忆基本上是保存用递归算法完成的过去操作的结果，以便在以后需要进行相同的计算时减少遍历递归树的需要。

参见http://scriptbucket.wordpress.com/2012/12/11/introduction-to-memoization/

Python中的斐波那契内存示例:

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

下面是一个解决方案，将工作与列表或dict类型参数没有抱怨:

def memoize(fn):
    """returns a memoized version of any function that can be called
    with the same list of arguments.
    Usage: foo = memoize(foo)"""

    def handle_item(x):
        if isinstance(x, dict):
            return make_tuple(sorted(x.items()))
        elif hasattr(x, '__iter__'):
            return make_tuple(x)
        else:
            return x

    def make_tuple(L):
        return tuple(handle_item(x) for x in L)

    def foo(*args, **kwargs):
        items_cache = make_tuple(sorted(kwargs.items()))
        args_cache = make_tuple(args)
        if (args_cache, items_cache) not in foo.past_calls:
            foo.past_calls[(args_cache, items_cache)] = fn(*args,**kwargs)
        return foo.past_calls[(args_cache, items_cache)]
    foo.past_calls = {}
    foo.__name__ = 'memoized_' + fn.__name__
    return foo

请注意，通过在handle_item中实现您自己的哈希函数，这种方法可以自然地扩展到任何对象。例如，为了使这种方法适用于一个接受set作为输入参数的函数，你可以在handle_item中添加:

if is_instance(x, set):
    return make_tuple(sorted(list(x)))