在递归函数中保持计数

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

试试这个，它适用于一般情况（任何键的值，不仅仅是'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)

Answer 2

这个方法效率很低，但应该能用：

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

你可以在线查看它的运行效果：ideone

这个方法的基本思路和你发的代码差不多，只是它每次只移动一个字符，而不是用 find 一下子跳到下一个匹配的地方。