Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Counting the character recursively

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 ?

like image 464
user3398505 Avatar asked Apr 09 '14 09:04

user3398505


2 Answers

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
like image 167
Martijn Pieters Avatar answered Oct 31 '22 14:10

Martijn Pieters


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 ;-)