Maximum recursion depth exceeded, but only when using a decorator

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.

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.

Trying to understand your code, I made some modifications. Nothing big, just a matter of preference.

I only changed one line:

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

for this one

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

As is, your code runs without any recursion problem

EDIT Testing it with the whole string you are using, I ran into recursion limit problem too. Definitely, it goes deep.

Add these 2 lines:

import syssys.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@memoizedef 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

Other than that, because you are using Python 3 (as I see in the question tag), you could use the functools.lru_cache instead of a custom memoize function:

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