Ведение счета в рекурсивной функции

Question

Я пытаюсь выяснить, как написать рекурсивную функцию (только с одним параметром), которая возвращает число раз, когда подстрока «ou» появляется в строке. Что меня смущает, так это то, что мне не разрешается использовать любые встроенные строковые функции, кроме len, или строковые операторы [] и [:] для индексации и объединения. Поэтому я не могу использовать встроенную функцию поиска

Я помню, что видел что-то подобное, но он использует два параметра, а также метод 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)