所有算术运算符都基于这样一个事实，即所有自然数都有一个后继数。出于教育目的，我将这个想法实现为Python函数：
# recursive definition of arithmetic operators
a = 2
b = 3 # larger numbers won't work: RecursionError
def successor(n):
""" returns n + 1. All other functions use successor recursively """
return n + 1
def sum(n, m):
""" sum a + b """
if m == 0:
return n
if m == 1:
return successor(n)
else:
return successor(sum(n, m - 1))
print(f"sum({a}, {b}) = {sum(a,b)}")
def product(n, m):
""" multiplication n*m"""
if m == 0:
return 0
elif m == 1:
return sum(n, 0)
else:
return sum(product(n, m - 1), n)
print(f"product({a}, {b}) = {product(a, b)}")
def power(n, m):
""" power n**m"""
if m == 0:
return 1
elif m == 1:
return product(n, 1)
else:
return product(power(n, m - 1), n)
print(f"power({a}, {b}) = {power(a, b)}")
def up_arrow_2(n, m):
""" up_arrow operator 2nd degree: n**(n**( ....) m times """
if m == 0:
return 1
elif m == 1:
return power(n, 1)
else:
return power(up_arrow_2(n, m - 1), n)
print(f"up_arrow_2({a}, {b}) = {up_arrow_2(a, b)}")
def up_arrow_3(n, m):
""" up_arrow operator 3rd degree"""
if m == 0:
return 1
elif m == 1:
return up_arrow_2(n, 1)
else:
return up_arrow_2(up_arrow_3(n, m - 1), n)
print(f"up_arrow_3({a}, {b}) = {up_arrow_3(a, b)}")
这对于最多为a=2和b=3的数字来说效果很好，然后在计算up_arrow_3(2, 4)时会发生maximum recursion depth exceeded(原因很明显(。
如果我插入return n**m行作为power函数内的第一行，那么可以计算出更大的数字。因此，缓存中间结果似乎是一个很有前途的解决方案。
为了扩展到更大的数字，我尝试使用装饰器类(如(进行记忆
class Memoize:
def __init__(self, fn):
self.fn = fn
self.memo = {}
def __call__(self, *args):
if args not in self.memo:
self.memo[args] = self.fn(*args)
return self.memo[args]
和装饰功能-没有成功。
我正在寻找一个如何编写另一个装饰器的想法，它可以进行所需的缓存并允许更大的输入数字a、b。
编辑：以下是@Urmzd使用蹦床制定的解决方案：
# recursive definition of arithmetic operators
from typing import Callable
a = 2
b = 3
def memoize(func):
cache = {}
def memoize_inner(*args, **kwargs):
str_args = f"{args}{kwargs}"
return cache.get(str_args, func(*args, **kwargs))
return memoize_inner
def trampoline(fn):
def trampoline_inner(*args, **kwargs):
fns = fn(*args, **kwargs)
while(isinstance(fns, Callable)):
fns = fns()
return fns
return trampoline_inner
def successor(n):
""" returns n + 1. All other functions use successor recursively """
return n + 1
@memoize
@trampoline
def _sum(n, m, cont=lambda x:x):
""" sum a + b """
return lambda: cont(n) if m == 0 else lambda: successor(_sum(n, m-1, lambda x: lambda: cont(x)))
@memoize
@trampoline
def product(n, m, cont=lambda x:x):
""" a*b """
return lambda: cont(n) if m == 1 else lambda: _sum(product(n, m-1, lambda x: lambda: cont(x)), n)
@memoize
@trampoline
def power(n, m, cont=lambda x:x):
""" a*b """
return lambda: cont(n) if m == 1 else lambda: product(power(n, m-1, lambda x: lambda: cont(x)), n)
@memoize
@trampoline
def ua2(n, m, cont=lambda x:x):
""" a*b """
return lambda: cont(n) if m == 1 else lambda: power(ua2(n, m-1, lambda x: lambda: cont(x)), n)
@memoize
@trampoline
def ua3(n, m, cont=lambda x:x):
""" a*b """
return lambda: cont(n) if m == 1 else lambda: ua2(ua3(n, m-1, lambda x: lambda: cont(x)), n)
print(f"sum({a}, {b}) = {_sum(a,b)}")
print(f"product({a}, {b}) = {product(a,b)}")
print(f"power({a}, {b}) = {power(a,b)}")
print(f"ua2({a}, {b}) = {ua2(a,b)}")
print(f"ua3({a}, {b}) = {ua3(a,b)}")
以下代码将解决您的问题。
def memoize(func):
cache = {}
def memoize_inner(*args, **kwargs):
str_args = f"{args}{kwargs}"
return cache.get(str_args, func(*args, **kwargs))
return memoize_inner
代码不起作用的部分原因是缺乏最优性。但这是一个完全不同的问题，可以通过各种方式解决。如果你想让记忆发挥作用，你必须记住你的所有功能。这确保了在每个级别上，冗余计算都有可能减少。
--编辑
如前所述，您的代码是次优的。部分原因是缺乏递归优化(使用延续的尾部递归，以及使用thunks和蹦床的堆栈优化(。
因此，让我们尝试一步一步地修复代码(递归优化的开销更大，因此应该尝试使用最少的工作量(。
首先，让我们修改sum函数，使其尾部递归(不需要继续(：
@memoize
def sum(n, m):
""" sum a + b """
return n if m == 0 else sum(successor(n), m-1))
或者，无论出于何种原因，如果您真的想使用continuation。
@memoize
def sum(n, m, cont=lambda x: x):
""" sum a + b """
return cont(n) if m == 0 else sum(successor(n), m-1)
然后，我们可以通过为lazy-evaluation:添加空lambda函数来使用thunks
@memoize
def sum(n, m, cont=lambda x: x):
""" sum a + b """
return lambda: cont(n) if m == 0 else lambda: sum(successor(n), m-1, lambda x: lambda: cont(x))
trampolines使用以下util函数开始递归：
from typing import Callable
def trampoline(fn):
while(isinstance(fn, Callable)):
fn = fn()
return fn
如果我们想调用函数，我们可以执行以下操作：
trampoline(sum(a,b))
然而，如果我们想隐含地调用暴徒，我们可以制作一个蹦床装饰器
def trampoline(fn):
def trampoline_inner(*args, **kwargs):
fns = fn(*args, **kwargs)
while(isinstance(fns, Callable)):
fns = fns()
return fns
return trampoline_inner
这样，您就应该拥有所有的工具来修复剩余的函数并防止递归深度错误。
完整的解决方案：
from typing import Callable
def memoize(func):
cache = {}
def memoize_inner(*args, **kwargs):
str_args = f"{args}{kwargs}"
return cache.get(str_args, func(*args, **kwargs))
return memoize_inner
def trampoline(fn):
def trampoline_inner(*args, **kwargs):
fns = fn(*args, **kwargs)
while(isinstance(fns, Callable)):
fns = fns()
return fns
return trampoline_inner
def successor(n):
""" returns n + 1. All other functions use successor recursively """
return n + 1
@memoize
@trampoline
def sum(n, m, cont=lambda x:x):
""" sum a + b """
return lambda: cont(n) if m == 0 else lambda: sum(successor(n), m-1, lambda x: lambda: cont(x))
print(f"sum({a}, {b}) = {sum(a,b)}")