递归计数字符

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. elif sentence[0] == 'm': 这行代码
2. slicing off last char with sentence[1:-1] 这行代码

// 注意，布尔值是整数类的一个派生类

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

Answer 2

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（例如，如果 s 为空或 None，那么 not s 就为真）。
2. 你并没有统计字符串中 m 出现的次数，所以应该有一些 count_so_far + recursive_call() 的写法。在你的情况下，由于你是一个字符一个字符地检查字符串，如果当前字符是 m，那么 count_so_far 就是 1，否则就是 0。
3. 要获取字符串中除了前 N 个字符以外的所有部分，正确的切片方式是 string[N:]。在 SO 上有一个关于切片的很好解释。

此外，这个例子是一个完美的尾递归算法的示例。这种算法可以用循环来表示，优点是只需在一个调用栈帧中执行。需要注意的是，很多编译器会将尾递归优化为循环，但这对 Python 解释器来说并不适用。

Answer 3

为了好玩，你可以把整个东西写成一个匿名的 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'))

同伴压力徽章，我们来了 ;-)

Answer 4

有两个问题：

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