递归计算字符

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]

这是我的代码.所以,如果count_m_recursive('my oh my')我得到2

代码有什么问题？

Answer 1

有两件事是错的:

1. 您正在切断每个递归调用的最后一个字符:

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

   不要限制调用s-1,不包括结束索引.

2. 当你m在开始时发现它时,你不想忽略其余的文本; 您的版本返回1并忽略字符串的其余部分.

您的功能适用于:

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

或者,简化:

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:])

甚至使用的事实,bool是的一个子类int和True为1时,False为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:])

演示:

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

为了好玩,您可以将整个事物编写为匿名lambda表达式,如下所示:

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徽章,我们来了;-)

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:])

概述当前实施中的一些问题:

1. 无需计算字符串的长度来检查它是否为空.空字符串等效False于布尔"上下文"(例如not s,如果s为空则为true None)
2. 你不总结m一个字符串的出现,所以应该有一些count_so_far + recursive_call().在您的情况下,因为您检查字符串char by char count_so_far是1,如果当前char是m,否则为0.
3. 正确切片以获得除前N个字符之外的所有字符串string[N:].在SO 上切片有一个很好的解释

此外,这是尾递归算法的完美示例.这种算法可以表示为循环,具有在一个调用堆栈帧中执行的优点.请注意,许多编译器无论如何都会优化尾递归以进行循环(但对于python解释器来说并非如此).