Python - Recursive Functions

Question

Below is the code that I am trying to execute: Recursively parse a string for a pattern that can be either 1 or 2 characters long.

def recur_parse(s,pattern):
   result = False
   print(s[0],s[0:2],result)
   if s[0]==pattern or s[0:2]==pattern:
     print('Condition Satisfied')
     return True
   elif len(s[1:]) >= len(pattern):
     print('Calling the function recurisively with params',s[1:],pattern)
     recur_parse(s[1:],pattern)
   else:
     return False

The expectation is that the recursive call should return a True, but it returns a False. Am I doing anything wrong?

The testcases execution for the same are below:

Case #1:

recur_parse('ximibi','xi')
('x', 'xi', False)
Condition Satisfied
=> True

Case #2:

recur_parse('ximibi','im')
('x', 'xi', False)
('Calling the function recurisively with params', 'imibi', 'im')
('i', 'im', False)
Condition Satisfied

Answer 1

It does not really return a False, but it returns None in the recursive case. Also, it always prints the initial value of the (never again used) variable result, which is False. To fix it, just add a return statement before the recursive call.

def recur_parse(s, pattern):
    if s[0] == pattern or s[0:2] == pattern:
        return True
    elif len(s[1:]) >= len(pattern):
        return recur_parse(s[1:], pattern)
    else:
        return False

You could also simplify the function to a single, more complex return statement (though whether that's simpler is certainly a matter of taste).

def recur_parse(s, pattern):
    return s[0] == pattern or s[0:2] == pattern \
            or len(s[1:]) >= len(pattern) and recur_parse(s[1:],pattern)

Answer 2

Your second case isn't returning False, it is returning None because you are not returning the result of the recursive call to recur_parse. Compare your code to the following function:

def recur_parse(s, pattern):
   if s[0] == pattern or s[0:2] == pattern:
     return True
   elif len(s[1:]) >= len(pattern):
     return recur_parse(s[1:], pattern) # notice the return here
   else:
     return False

However, this only works with patterns that are of length 1 or 2. This can be extended with str.startswith.

def has_string(s, m):
    return s.startswith(m) or bool(s) and has_string(s[1:], m)

Note that here bool(s) is the base case. Whether or not this is readable is above my pay grade.

If this wasn't a practice in recursion, you'd want to use:

def has_string(s, m):
    return m in s

Answer 3

def recur_parse(s,pattern):
    if (len(s) < len(pattern)):
        return False
    if (s[0:len(pattern)] == pattern):
        return True
    return recur_parse(s[1:],pattern)

Changed so it is slightly more robust: Should work with patterns of n length.

1. You should be returning the result of the recursive function so you know the result further down the line.
2. Your Result variable does nothing
3. You should probably check the length at the start of the function in case a String shorter than the pattern is passed to begin with
4. You can remove one of the conditional statements with the position of the return statements.

The first part of the recursive statement checks for the edge cases: Where you either know, explicitly, that the String is valid or invalid. Finally, the recursive step assumes that the two edge cases failed, hence try again until one passes.