Using Recursion to Replace all occurences of a substring with another substring

Recursively you know that your function applied to:

• base case) An empty string, must return an empty string;
• rec case) A string starting with b, must replace b with a and check the rest of the string;
• rec case) Else, return the first character of the string chained to rest of the string returned recursively

Here is the algorithm:

def rec_replace(string, a, b):
    if not string: #if the string is empty
        return ""
    elif string[:len(b)] == b: #if the string start with b, replace it with a
        return a + rec_replace(string[len(b):], a, b)
    else: #else, add this character and go to the next one
        return string[0] + rec_replace(string[1:], a, b)

Test:

print rec_replace("hello this is hello a simple hello test", "ok", "hello")

Output:

ok this is ok a simple ok test