Python code with recursive functions returning None | Input and Output provided

Question

I having been impoving myself in Python for a while. I executed this code but never seem to get either True or False for my output which I actually require.

def cathat(str,cat,hat):

    #print("Cat: {} Hat: {} Strlen: {}".format(cat,hat,len(str)))
    if len(str) is 0:
        if cat == hat:
            print("True") #For debugging purpose
            return True
        else:
            print("False") #For debugging purpose
            return False

    else:
        if str.startswith("cat"):
            cathat(str[3:],cat + 1,hat)
        elif str.startswith("hat"):
            cathat(str[3:],cat,hat + 1)
        else:
            cathat(str[1:],cat,hat)

            
def cat_hat(str):
  return cathat(str, 0, 0)

For Input:

2
catinahat
bazingaa

Your Output is:

True
None
True
None

Expected Output is:

True
True

Samwise · Accepted Answer · 2020-07-18T16:32:13.633

This block of your code executes cathat but doesn't do anything with its result:

    else:
        if str.startswith("cat"):
            cathat(str[3:],cat + 1,hat)
        elif str.startswith("hat"):
            cathat(str[3:],cat,hat + 1)
        else:
            cathat(str[1:],cat,hat)

You want to return cathat(...) in all of these cases.

Note: str is a bad name for a variable, because it overrides the builtin type/function str!

def cat_hat(string: str, cat: int = 0, hat: int = 0, debug: bool = False) -> bool:
    if debug:
        print(f"Cat: {cat} Hat: {hat} String: '{string}'")
    if len(string) == 0:
        if debug:
            print(f"returning {cat == hat}")
        return cat == hat
    else:
        if string.startswith("cat"):
            return cat_hat(string[3:], cat + 1, hat, debug)
        elif string.startswith("hat"):
            return cat_hat(string[3:], cat, hat + 1, debug)
        else:
            return cat_hat(string[1:], cat, hat, debug)


cat_hat("catinahat", debug=True)

prints:

Cat: 0 Hat: 0 String: 'catinahat'
Cat: 1 Hat: 0 String: 'inahat'
Cat: 1 Hat: 0 String: 'nahat'
Cat: 1 Hat: 0 String: 'ahat'
Cat: 1 Hat: 0 String: 'hat'
Cat: 1 Hat: 1 String: ''
returning True

score 0 · Answer 2 · answered Jul 18 '20 at 17:07

You've made an error common to folks new to recursion in that if your recursive function returns a value, and you call it recursively, you need to deal with that value. Whether you need to do further processing on that result or not.

Also, if a return or break end the body of an if statement, you don't need the explicit else or elif as that code isn't going to be executed anyway:

def cat_hat(string, cat=0, hat=0):
    if not string:
        return cat == hat

    if string.startswith("cat"):
        return cat_hat(string[3:], cat + 1, hat)

    if string.startswith("hat"):
        return cat_hat(string[3:], cat, hat + 1)

    return cat_hat(string[1:], cat, hat)

print(cat_hat("catinahat"))  # both 1
print(cat_hat("bazingaa"))  # both 0
print(cat_hat("Watch me pull a rabbit out of my hat.")) # hat > cat

OUTPUT

> python3 test.py
True
True
False
>

A +1 to @OlvinRoght regarding is vs. == and @Samwise regarding redefining str.

Python code with recursive functions returning None | Input and Output provided

2 Answers2