Python string recursion

Question

I have to recursively replace characters in a string with new characters. I'm a bit stuck right now, however. I cannot import anything, so here is my code:

EDIT: I forgot to mention that I'm not allowed to use any built in functions besides len() and index/splice operators. This means I can't use 'in'. This is a homework question, but I don't expect you guys to solve it for me, just to point out why my code isn't working. Thanks!

def replace_char(astr, old_char, new_char):
    newstr = ""
    if astr == "":
        return newstr
    elif astr[0] == old_char:
        newstr += new_char
        return replace_char(astr[1:], old_char, new_char)
    else:
        newstr += astr[0]
        return replace_char(astr[1:], old_char, new_char)

Any ideas on why it isn't working? Thanks!

you make newstring empty everytime you call it ... but then you try to add to it ... — Joran Beasley, Mar 23 '15 at 17:01
possible duplicate of [Change one character in a string in Python?](http://stackoverflow.com/questions/1228299/change-one-character-in-a-string-in-python) — Tui Popenoe, Mar 23 '15 at 18:19

score 1 · Accepted Answer · answered Mar 23 '15 at 17:08

Here's what you're looking for:

def replace_char(astr, old_char, new_char):
    if astr == "":
        return astr
    elif astr[0] == old_char:
        return new_char + replace_char(astr[1:], old_char, new_char)
    else:
        return astr[0] + replace_char(astr[1:], old_char, new_char)

The only string you ever returned in your old code was an empty one:

newstr = ""
    if astr == "":
        return newstr

You need to be adding characters to your return value as you recurse through the string.

score 0 · Answer 2 · answered Mar 23 '15 at 17:07

def replace_char(s, old, new):
    if len(s) == 0:
        return ''
    elif len(s) == 1:
        if s == old:
            return new
        else:
            return s
    else:
        return replace_char(s[0], old, new) + replace_char(s[1:], old, new)

>>> replace_char('test', 't', 'c')
'cesc'

score 0 · Answer 3 · answered Mar 23 '15 at 17:09

@Joran Beasley is right -- you recreate newstr each time you go through the function. Change the function header to include newstr:

def replace_char(astr, old_char, new_char, newstr = '')

And change all the calls to the function as well:

return replace_char(astr[1:], old_char, new_char, newstr)

Here's the full code:

def replace_char(astr, old_char, new_char, newstr = ''):
    newstr = ""
    if astr == "":
        return newstr
    elif astr[0] == old_char:
        newstr += new_char
        return replace_char(astr[1:], old_char, new_char, newstr)
    else:
        newstr += astr[0]
        return replace_char(astr[1:], old_char, new_char, newstr)

This implementation keeps most of your existing code in place, but it would make far more sense to use astr.replace(old_char, new_char) in most situations

score 0 · Answer 4 · answered Mar 23 '15 at 17:11

0

def replace_chr(a_string,old,new):
    if not a_string:return a_string
    next_char = a_string[0] if a_string[0] != old else new
    return next_char + replace_chr(a_string[1:],old,new)

answered Mar 23 '15 at 17:11

Joran Beasley

110,522
12
160
179

Python string recursion

4 Answers4