python - 在递归函数中保持计数

Question

我试图弄清楚如何编写一个递归函数（只有一个参数），它返回子字符串“ou”在字符串中出现的次数。我感到困惑的是，我不允许使用除 len 或字符串运算符 [] 和 [:] 之外的任何内置字符串函数进行索引和拼接。所以我不能使用 find 内置的查找功能

我记得看到过这样的东西，但是它使用了两个参数并且还使用了 find() 方法

def count_it(target, key):
  index = target.find(key)
  if index >= 0:
    return 1 + count_it(target[index+len(key):], key)
  else:
    return 0

Answer 1

非常低效，但应该工作：

def count_it(target):
    if len(target) < 2:
        return 0
    else:
        return (target[:2] == 'ou') + count_it(target[1:])

在线查看它：ideone

它与您发布的代码基本相同，只是它一次仅在字符串中移动一个字符，而不是find用于跳转到下一个匹配项。

Answer 2

试试这个，它适用于一般情况（任何键值，不仅仅是'ou'）：

def count_it(target, key):
    if len(target) < len(key):
        return 0
    found = True
    for i in xrange(len(key)):
        if target[i] != key[i]:
            found = False
            break
    if found:
        return 1 + count_it(target[len(key):], key)
    else:
        return count_it(target[1:], key)