Counting the character recursively

Question

def count_m_recursive(sentence):
    s = len(sentence) 
    if s == 0:
        return 0
    elif sentence[0] == 'm':
        return 1
    else:
        return count_m_recursive(sentence[1:s-1]

This is my code. So if count_m_recursive('my oh my') I should get 2

What is wrong with the code ?

Answer 1

Two things are wrong:

1. You are cutting off the last character on each recursive call:

   return count_m_recursive(sentence[1:s-1])
   

   Don't limit the call to s-1, the end index is not included.

2. You don't want to ignore the rest of the text when you find an m at the start; your version returns 1 and ignores the rest of the string.

Your function works with:

elif sentence[0] == 'm':
    return 1 + count_m_recursive(sentence[1:])
else:
    return count_m_recursive(sentence[1:])

or, simplified:

def count_m_recursive(sentence):
    if not sentence:  # an empty string tests false
        return 0
    return (1 if sentence[0] == 'm' else 0) + count_m_recursive(sentence[1:])

or even use the fact that bool is a subclass of int and True is 1, False is 0:

def count_m_recursive(sentence):
    if not sentence:  # an empty string tests false
        return 0
    return (sentence[0] == 'm') + count_m_recursive(sentence[1:])

Demo:

>>> def count_m_recursive(sentence):
...     if not sentence:  # an empty string tests false
...         return 0
...     return (sentence[0] == 'm') + count_m_recursive(sentence[1:])
... 
>>> count_m_recursive('my oh my')
2

Answer 2

For the fun, you can write the entire thing as an anonymous lambda expression as follows:

def make_funny_func():
    # wrapped the code with return clause to emphasize that it is 
    # anonymous ;)
    return (
        # Y combinator
        (lambda f: (lambda x: x(x))(lambda y: f(lambda a: y(y)(a))))
        # our function wrapped
        (lambda count:
            lambda s:
                # return 1 + f(s[1:]) if the first character is 'm'
                # 0 + f(s[1:]) otherwise.
                (s[0] == 'm') + count(s[1:])
                # but do the thing before only if s is non-empty string
                if s
                # else return 0
                else 0
        )
    )

count_m_recursive = make_funny_func()
print(count_m_recursive('mmmkay'))

Peer pessure badge, here we come ;-)

Answer 3

def count_m_recursive(sentence): #mmmm
    if not sentence:
        return 0
    m_first = 1 if sentence[0] == 'm' else 0
    return m_first + count_m_recursive(sentence[1:])

To outline some issues in current implementation:

1. No need to calculate length of a string to check if it's empty. Empty strings are equivivalent to False in boolean "context" (e.g. not s is true if s is empty or None)
2. You don't sum up occurences of the m in a string, so there should be some count_so_far + recursive_call(). In your case, since you examine string char by char count_so_far is 1 if current char is m, 0 otherwise.
3. Proper slicing to get the all the string except first N chars would be string[N:]. There's a good explanation of slicing on SO

Also, this is a perfect example of tail recursive algorithm. Such kinds of algorithms can be expressed as a loop with advantage of executing in one call stack frame. Note that a lot of compilers optimize tail recursion to loop anyway (but that's not true for python interpreter).

Answer 4

Problem is with

1. elif sentence[0] == 'm':
2. slicing off last char with sentence[1:-1]

// Note Boolean is derived class of integer class

def count_m_recursive(sentence):
    return (sentence or 0 ) and ((sentence[0] == 'm') + count_m_recursive(sentence[1:]))