NOTE: I edited your post for readability, adding a code block so it’s a bit clearer.
So this might not be the ideal exercise as the recursive solution is a little involved. I’ll just put a possible solution here - it could be a lot more concise, but I’ve tried to make it a bit more verbose so you can see each condition. You need to be really careful to explicitly handle every possible case, else you can very easily get into infinite recursion situations.
It’s easy enough to write a recursive function if text1
is a single character.
So for a function check(char, text)
where char
is a single character and text
is the string you’re going to recurse over:
- if the length both the character and the text are 0, return True (exit as soon as possible if this is the case, this is a sanity check to stop the function erroring if
""
and ""
get passed as arguments).
- If the character is found in
text
, return True.
- If the length of text is 0, return False (it is important that this comes after the two conditions above).
- Otherwise run the function again with the first character from
text
dropped.
def check(char, text):
if len(char) == 0 and len(text) == 0:
return True
if len(text) == 0:
return False
if char == text[0]:
return True
else:
return check(char, text[1:])
check("o", "hello")
You can step through this here.
But you want to check if a set of characters appears in the text. So we need to change the conditions slightly.
- If the length of text1 is greater than text2, it isn’t possible for text1 to be in text2, so return False (this replaces the len(text) == 0 check in the first function).
- If the length both the character and the text are 0, return True.
- If text1[0] == text2[0], need to check that text1[1] == text2[1] and so on, so we’ll split that out into another function.
i. if that returns True, return True in the main function.
ii. if it doesn’t, run the main function again with the first character in text2
dropped.
def check(text1, text2):
if len(text1) > len(text2):
return False
if len(text1) == 0 and len(text2) == 0:
return True
if text1[0] == text1[0]:
subcheck = substring_check(text1, text2)
if subcheck:
return True
else:
return check(text1, text2[1:])
def substring_check(str1, str2):
if (len(str1) == 0):
return True
if (str1[0] != str2[0]):
return False
else:
return substring_check(str1[1:], str2[1:])
check("llo", "hello")
Step through the code here
Apologies if there are any typing mistakes there, but hopefully that should be somewhat helpful.