Python Maximum depth recursion error - issue with base case

Question

I wrote a python function replace_str that consumes 3 non-empty strings, base, target and rep.

The first string, base represents a base string that you want to update. The second string target represents the target string that you want to replace and the third string rep represents a string that will replace the target in the updated string.

The function produces a new string in which the target string is replaced by the rep string in the base string, but produces the same base string if either of the following conditions hold true.

• If the target string is not found in the base string or,

• If the target and rep are the same strings.

NOT allowed to use the string methods replace and find

This is what I have so far:

def replace_str(base, target, rep): 
    m = 0
    n = len(target)
    if base[m:n] == target:
        new_base = base[0:m] + rep + base[n:]
        return replace_str(new_base, target, rep)
    else:
        m = m + 1
        n = n + 1
        return replace_str(base, target, rep)

I'm getting a maximum recursion depth error when I test my program. I'm trying various base cases, as that's where my function gets stuck, but all the base cases I try give me either '' or the last letter of the base

replace_str("aaaax","aa","x") should produce 'aax' but gives me an error.

replace_str("aa", "aa", "x") however gives me the correct result of 'x'.

Also, this post isn't a duplicate of the other one. The program with the linked post is entirely different and has a different issue. I'm having problems with my base case.

`m = m + 1` is useless because `m` is not used after that. consider calling `return base[0] + replace_str(base[1:], target, rep)` — njzk2, Jul 07 '15 at 19:44
It would be useful if you told us which strings you’re testing with that give this error. — alexwlchan, Jul 07 '15 at 19:44
Both branches are always going to call `replace_str` again. It can never escape. — Peter Wood, Jul 07 '15 at 19:44
@alexwlchan its for any strings that I test. I think there might be an error for the recursion when it reaches the base case, but I don't really get what it might be — Shagun Chhikara, Jul 07 '15 at 19:48
@njzk2 yeah I have the code with the program without recursion but I'm being tested on recursion in python — Shagun Chhikara, Jul 07 '15 at 19:49
@PeterWood I noticed that and tried to add a base case but any base case I try returns '' or the last letter of the base — Shagun Chhikara, Jul 07 '15 at 19:51
You do not have a base case. There is no codepath here in which a result is returned at all. Your `return` statements are always invoking the function, so you recurse infinitely. — sirosen, Jul 07 '15 at 19:51
@sirosen I'm having trouble writing the base case as all of the possibilities I try give me '' or the last letter of the base — Shagun Chhikara, Jul 07 '15 at 19:52
Look at the comment above yours. You never return anything. With recursion you always have to have a termination or base case, where something concrete is returned. You only ever recursively call the function, so it will recurse infinitely — J Richard Snape, Jul 07 '15 at 19:52
Show us your simplest test case, as small a string as possible, and what you expect the result to be. — Peter Wood, Jul 07 '15 at 19:54
Thanks for updating with the test case. However, there is no way `replace_str("aa", "aa", "x")` returns `'x'` — Peter Wood, Jul 07 '15 at 20:07
@PeterWood oh whoops you're right. replace_str("aa", "aa", "x") returned 'x' when I made the base case if n == len(base): return base but that still gives an error for the other test — Shagun Chhikara, Jul 07 '15 at 20:10
Your base case `is a recursive call`. You can't stop recursing if you only return a recursive call. You have to have some point (base case) where the code returns something that isn't a recursive call so the program stops stepping into the stack. — Matt, Jul 08 '15 at 01:00
You say that `replace_str("aaaax","aa","x")` should produce `'aax'` but considering the description it should produce `'xxx'` instead, shouldn't it? — dlask, Jul 08 '15 at 01:25

score 0 · Answer 1 · answered Jul 08 '15 at 01:21

In your else branch you update m and n, but you cannot pass those values on to the next call to replace_str, which ends up starting again from the beginning.

You need to either add m and n as arguments, or turn that part of the function into a loop.

Using extra arguments is easier, and looks something like this:

# adding m and n as arguments
def replace_str(base, target, rep, m=0, n=None):
    if n is None:
        n = len(target)
    ...

You also need a base case, the easiest of which is probably:

# adding m and n as arguments
def replace_str(base, target, rep, m=0, n=None):
    if target not in base:
        return base
    if n is None:
        n = len(target)
    ...

Python Maximum depth recursion error - issue with base case

1 Answers1