Recursive function that identifies whether string 1 is contained within string 2? (Python 3.4)

Question

Is there a way to write a recursive (required) function that takes two strings as parameters and returns True if all characters in the first string can be found, in order, in the second string; and False otherwise?

For example:

>>> contains("lit", "litter")
True
>>> contains("thot", "thurtle")
False
>>> contains("ratchet", "ramtbunchiousest")
True
>>> contains("shade", "hadsazie")
False

The letters don't need to be consecutive (as in the third example), but they need to be in order (which is why the fourth example fails).

I wrote this code:

def contains_recursive(s1, s2):

if s1 == "":
    return True
elif s1[0] == s2[0]:
    return contains_recursive(s1[1:], s2[1:])
elif s1[0] != s2[0]:
    return contains_recursive(s1[0], s2[1:])
else:
    return False

return contains_recursive(s1, s2) == True

and it gave out this error:

IndexError: string index out of range

What should I do to fix the problem?

Answer 1

At the line:

 return contains_recursive(s1[0], s2[1:])

you are shortening s1 to one character but then at the next call you may hit:

 return contains_recursive(s1[1:], s2[1:])

with s1 a string of len 1.

You need to use:

return contains_recursive(s1, s2[1:])

and add a check on the length of s1

Answer 2

The error you are getting could be because s2 is an empty string. Add a check for it's length as well. If you reach this point it would mean you haven't found all the letters you are searching for and therefore the end result should be false.

if s2 == '':
    return False