Maximum recursion depth exceeded, but only when using a decorator

Question

I'm writing a program to calculate Levenshtein distance in Python. I implemented memoization because I am running the algorithm recursively. My original function implemented the memoization in the function itself. Here's what it looks like:

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

This works! However, I found a way to memoize using decorators. I tried to apply this technique to my algorithm:

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

To me, this looks cleaner and less confusing. I thought that the two would be functionally equivalent, but when I ran the version with the decorator, I was surprised to find that I got a RecursionError: maximum recursion depth exceeded.

What exactly am I missing? Is using the decorator not functionally equivalent? I attempted a fix by adding sys.setrecursionlimit(1500) and this works, but it is a hack and doesn't explain why the two function differently.

NOTE: I am using one paragraph of lorem ipsum as my test strings for s and t from Wikipedia:

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.

I understand that for even longer strings, my first function will fail. I just want to know why the decorated one fails first. Thanks!

Answer 1

Consider the stack frames (function calls) that are happening in your original code. They will look something like:

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

In you memoized version they appear as:

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

That is, your stack frame will be twice as big, as each "call" actually invokes two functions. Thus you will exhaust the stack frame limit earlier.

Answer 2

This looks like an infinite recursion issue, but it's not. You're just recursing really deeply, and the decorator makes it deeper.

Instead of directly calling the lev function you defined, every call goes through wrap, and wrap calls lev. That makes your call stack twice as deep. You would have run into this problem anyway if you didn't use the decorator and your inputs got bigger.

To fix this, you'll probably have to switch to a non-recursive program structure, either by using a bottom-up dynamic programming style or by converting the recursion to iteration and maintaining a stack manually.