title: Maximum recursion depth exceeded, but only when using a decorator
body: <p>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:</p>
  
  <pre><code># 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)
  </code></pre>
  
  <p>This works! However, I found a way to memoize <a href="http://www.python-course.eu/python3_memoization.php">using decorators</a>. I tried to apply this technique to my algorithm:</p>
  
  <pre><code># 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)
  </code></pre>
  
  <p>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 <code>RecursionError: maximum recursion depth exceeded</code>.</p>
  
  <p>What exactly am I missing? Is using the decorator not functionally equivalent? I attempted a fix by adding <code>sys.setrecursionlimit(1500)</code> and this works, but it is a hack and doesn't explain why the two function differently. </p>
  
  <p>NOTE: I am using one paragraph of lorem ipsum as my test strings for s and t from Wikipedia:</p>
  
  <blockquote>
    <p>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.</p>
  </blockquote>
  
  <p>I understand that for even longer strings, my first function will fail. I just want to know why the decorated one fails first. Thanks!</p>