算術運算子的遞回定義：如何記憶/快取？

所有算術運算子都基于這樣一個事實，即所有自然數都有后繼。出于教育目的，我將這個想法實作為 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，然后maximum recursion depth exceeded計算發生時up_arrow_3(2, 4)（這也是為什么相當明顯）。

如果我將該行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)}")

uj5u.com熱心網友回復：

以下代碼將解決您的問題。

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

您的代碼不起作用的部分原因是缺乏優化。但這是一個完全不同的問題，可以通過多種方式解決。如果你想讓記憶起作用，你必須記住你所有的功能。這確保在每個級別，冗余計算可能會減少。

- 編輯

如前所述，您的代碼是次優的。部分原因是缺乏遞回優化（使用延續的尾遞回，以及使用 thunk 和蹦床的堆疊優化）。

因此，讓我們嘗試一次一步修復您的代碼（遞回優化的開銷更大，因此應嘗試使用最少的作業量）。

首先，讓我們修改sum函式以使其成為尾遞回（不需要延續）：

@memoize
def sum(n, m):
    """ sum a   b """
    return n if m == 0 else sum(successor(n), m-1))

或者，如果您出于任何原因真的想使用延續。

@memoize
def sum(n, m, cont=lambda x: x):
    """ sum a   b """
    return cont(n) if m == 0 else sum(successor(n), m-1)

然后，我們可以thunks通過添加空的 lambda 函式來使用lazy-evaluation：

@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))

但是，如果我們想隱式呼叫thunk，我們可以制作一個蹦床裝飾器

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)}")

標籤：Python 递归

上一篇：如何撰寫Selenium自動化測驗的偽代碼？

下一篇：求和串列中每個元素索引的最大值