超出最大递归深度，但仅在使用装饰器时

Question

我正在编写一个程序来计算 Python 中的 Levenshtein 距离。我实现了记忆化，因为我是运行递归算法。我的原始函数在函数本身中实现了记忆。这是它的样子：

# Memoization table mapping from a tuple of two strings to their Levenshtein distance
dp = {}

# Levenshtein distance algorithm
def lev(s, t):

  # If the strings are 0, return length of other
  if not s:
    return len(t)
  if not t:
    return len(s)

  # If the last two characters are the same, no cost. Otherwise, cost of 1
  if s[-1] is t[-1]:
    cost = 0
  else:
    cost = 1

  # Save in dictionary if never calculated before
  if not (s[:-1], t) in dp:
    dp[(s[:-1], t)] = lev(s[:-1], t)
  if not (s, t[:-1]) in dp:
    dp[(s, t[:-1])] = lev(s, t[:-1])
  if not (s[:-1], t[:-1]) in dp:
    dp[(s[:-1], t[:-1])] = lev(s[:-1], t[:-1])

  # Returns minimum chars to delete from s, t, and both
  return min(dp[(s[:-1], t)] + 1,
             dp[(s, t[:-1])] + 1,
             dp[(s[:-1], t[:-1])] + cost)

这有效！但是，我找到了一种记忆 using decorators 的方法。我尝试将此技术应用到我的算法中：

# Memoization table mapping from a tuple of two strings to their Levenshtein distance
def memoize(func):
  memo = {}
  def wrap(s, t):
    if (s, t) not in memo:
      memo[(s, t)] = func(s, t)
    return memo[(s, t)]
  return wrap

# Levenshtein distance algorithm
@memoize # lev = memoize(lev)
def lev(s, t):

  # If the strings are 0, return length of other
  if not s:
    return len(t)
  if not t:
    return len(s)

  # If the last two characters are the same, no cost. Otherwise, cost of 1
  if s[-1] is t[-1]:
    cost = 0
  else:
    cost = 1

  # Returns minimum chars to delete from s, t, and both
  return min(lev(s[:-1], t) + 1,
             lev(s, t[:-1]) + 1,
             lev(s[:-1], t[:-1]) + cost)

对我来说，这看起来更清晰，也更容易混淆。我以为这两者在功能上是等价的，但是当我运行带有装饰器的版本时，我惊讶地发现我得到了一个 RecursionError: maximum recursion depth exceeded.

我到底错过了什么？使用装饰器在功能上不等价吗？我尝试通过添加 sys.setrecursionlimit(1500) 进行修复，这很有效，但这是一种 hack，并没有解释为什么两者的功能不同。

注意：我使用一段 lorem ipsum 作为维基百科中 s 和 t 的测试字符串：

Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est labour.

我知道对于更长的字符串，我的第一个函数将失败。我只想知道为什么装饰的首先失败。谢谢！

Answer 1

考虑原始代码中发生的堆栈帧（函数调用）。它们看起来像：

lev(s, t)
-> lev(..., ...)
   -> lev(..., ...)
       -> lev(..., ...)
           -> lev(..., ...)

在您记忆的版本中，它们显示为：

wraps(s, t)
-> lev(..., ...)
   -> wraps(s, t)
      -> lev(..., ...)
          -> wraps(s, t)
             -> lev(..., ...)
                -> wraps(s, t)
                   -> lev(..., ...)
                      -> wraps(s, t)
                         -> lev(..., ...)

也就是说，您的堆栈帧将是两倍大，因为每个 "call" 实际上调用两个函数。因此，您将更早地耗尽堆栈帧限制。

Answer 2

这个看起来像一个无限递归问题，但事实并非如此。你只是递归得非常深，而装饰器让它更深。

不是直接调用您定义的 lev 函数，而是每次调用都经过 wrap，并且 wrap 调用 lev。这使您的调用堆栈深度加倍。如果您不使用装饰器并且您的输入变大，您无论如何都会运行遇到这个问题。

要解决此问题，您可能必须切换到非递归程序结构，方法是使用自下而上的动态编程风格或将递归转换为迭代并手动维护堆栈。

Answer 3

为了理解您的代码，我做了一些修改。没什么大不了的，只是一个偏好问题。

我只改了一行：

if s[-1] is t[-1]:

这个

if s[-1] == t[-1]:

照原样，您的代码运行时没有任何递归问题

EDIT 用你正在使用的整个字符串测试它，我也运行遇到了递归限制问题。当然，它深入。

添加这两行：

import sys
sys.setrecursionlimit(10000) 

def memoize(func):
  memo = {}
  def wrap(s, t):
    if (s, t) not in memo:
      memo[(s, t)] = func(s, t)
    return memo[(s, t)]
  return wrap

@memoize
def lev(s, t):
    len_s, len_t = len(s), len(t)
    if len_s==0: return len_t
    if len_t==0: return len_s
    cost = 0 if s[-1] == t[-1] else 1
    return min(lev(s[:-1], t) + 1,
               lev(s, t[:-1]) + 1,
               lev(s[:-1], t[:-1]) + cost)

s = "Lorem ibsum +++"
t = "Loren ipsum ..."
print(lev(s, t))             # 5

除此之外，因为您使用的是 Python 3（正如我在问题标签中看到的），您可以使用 functools.lru_cache 而不是自定义 memoize 函数：

from functools import lru_cache

@lru_cache(maxsize=None)
def lev(s, t):
    ...
    ...

超出最大递归深度，但仅在使用装饰器时

Maximum recursion depth exceeded, but only when using a decorator

python

python-3.x

recursion

decorator

memoization