Как провести подсчет в рекурсивной функции? [Python]

Вот что-то похожее на ответ Грега Хьюгилла. Однако вместо этого мы каждый раз при вызове функции проходим по текущему счету, а затем возвращаем счет, когда больше не нужно делать никаких совпадений. Хотя я подозреваю, что на Python это не имеет никакого значения, в языках, реализующих рекурсию tail-call, это позволяет оптимизировать каждый последующий вызов do_count на стеке вызовов. Это означает, что каждый вызов к do_count не приводит к росту стека вызовов.

def count_sub_strings(target, key):
    def do_count(target, key, count):
        index = target.find(key)
        if index >= 0:
            target = target[index + len(key):]
            return do_count(target, key, count + 1)
        else:
            return count
    return "No. of instances of %s in %s is %s" % (key, target, do_count(target, key, 0))

Одним из способов модификации вашего кода было бы использование локальной функции следующим образом:

def countSubStringMatchRecursive(target,key):
    def countit(target,key,count):
        index=find(target,key)
        if index>=0:
            target=target[index+len(key):]
            count += countit(target,key,count) + 1
        return count
    return "No. of instances of", key, 'in', target, 'is', countit(target,key,0)

Только сбоку. , но стоит исправить, если так ;-). Рассмотрим:

>>> 'banana'.count('ana')
1
>>> sum('banana'[x:x+3]=='ana' for x in range(len('banana')))
2

Первое выражение подсчитывает не перекрывающихся вхождений «Ана» в «банане»; Второй подсчет Все вхождений - во всех случаях есть два вхождения, по индексам 1 и 3 в «банане», и они перекрываются. Так что дано заявление о проблеме, и я цитирую:

Найти нет. экземпляров Подстрока в родительской строке.

Без упоминания о «не перекрывающемся положении», кажется, что перекрывающиеся вхождения должны учитываться . Конечно, это легко исправить, однажды заметили - вам просто придется продвигаться на 1 каждый раз, вместо того, чтобы продвигаться Len (ключ) , который приводит вас к пропуску перекрывающихся вхождений.

Итак, например:

import string

def countit(target, key, startfrom=0):
    where = string.find(target, key, startfrom)
    if where < 0: return 0
    return 1 + countit(target, key, where+1)

print countit('banana', 'ana')

Отпечатки 2 , подсчет как (перекрывающихся) вхождений.

Другой способ иметь третий дополнительный параметр На функцию CountSubstringMatchRecursive функция называется подсчетом, которое первоначально устанавливается на 0 . Таким образом, вы могли бы отслеживать количество. Это будет разоблачить переменную счет к внешнему миру, который может не быть желательным, но так как он не хуже, чем ваша глобальная переменная, я не думаю, что это будет проблема в вашем случае.

Вы также должны были бы изменить код, чтобы сделать последний рекурсивный звонок, который будет вызовом, который дает оператор возврата к внешнему миру. См. В этом примере (непроверенном):

def countSubStringMatchRecursive(target, key, count = 0):
    index = find(target, key)
    targetstring = target
    if index >= 0:
        count += 1
        target = target[index+len(key):]
        countSubStringMatchRecursive(target, key, count)
    else:
        return "No. of instances of", key, 'in', targetstring, 'is', count

Редактировать: Я понял, что вам понадобится четвертый параметр, чтобы иметь возможность сохранить исходную строку, перемещаемое вдоль рекурсии. Это, вероятно, менее оптимальное решение, и я бы порекомендовал использовать решение Greg Hewgill. Он имеет чистое разделение между взаимодействием со внешней и «бизнес-логикой», что делает код более многоразовым!

Не непроверенный...

code:

def countSubStringMatchRecursive(target, key, count=0):
    #### index = find(target, key) # HUH?
    index = target.find(key)
    if index >= 0:
        count += 1
        target = target[index+len(key):]
        count = countSubStringMatchRecursive(target, key, count)
    return count

for test in ['', 'bar', 'foo', 'foofoo', 'foo foo foo fo']:
   print countSubStringMatchRecursive(test, 'foo'), test.count(key), repr(test)

output:

0 0 ''
0 0 'bar'
1 1 'foo'
2 2 'foofoo'
3 3 'foo foo foo fo'

Я предполагаю, что это просто развлечение или домашнее задание ... рекурсивная функция должна быть медленнее, чем соответствующее итерационное решение на питоне, которое естественно будет медленнее, чем использование target. count(key) ... так что я не потрудился исправить все проблемы, которые были в вашей версии ... но почитайте PEP-008 :-)

Комментарии к строковому модулю

Вы прокомментировали, что пропустили из строкового import find. Какую версию Python вы используете? Какая дата последнего обновления используемой вами книги или учебника?

С самого начала работы со строковым модулем (он будет на вашем компьютере как <каталог установки Python>/Lib/string.py; цитирую из версии 2.6):

" "Коллекция строковых операций (большинство из них больше не используется).

Предупреждение: большая часть кода, который вы видите здесь, в настоящее время обычно не используется. Начиная с Python 1.6, многие из этих функций реализованы как методы на стандартном строковом объекте. Раньше они реализовывались с помощью встроенный модуль под названием strop, но strop теперь сам устарел.

и т.д. ""

и вот код этого файла для функции find (лишен комментариев):

def find(s, *args):
    return s.find(*args)

поэтому использование string.find(target, key) вместо target.find(key) является пустой тратой времени.

Ваша рекурсивная функция имеет производительность O (n ^ 2), потому что она копирует оставшееся содержимое строки каждый раз, когда он находит совпадение. Это медленнее, чем итеративное решение o (n) и без необходимости.

Вы можете легко переписать его быстрее, и в то же время упростить код и расширить его функциональность, передавая индекс запуска для поиска в качестве необязательного параметра к функции:

def countSubStringMatchRecursive(target, key, start_index = 0):
    index = target.find(key, start_index)
    if index >= 0:
        return countSubStringMatchRecursive(target, key, index + len(key)) + 1
    return 0

target_string = 'an apple and a banana'
key = 'an'
count = countSubStringMatchRecursive(target_string,  key)
print "Number of instances of %r in %r is %d" % (key, target_string, count)

Вывод:

Number of instances of 'an' in 'an apple and a banana' is 4

Обновление: Если вы действительно хотите использовать функцию находки String Module, вы можете сделать это, просто изменив одну строку:

index = find(target, key, start_index)

Как насчет этого?

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


print count_it("aaa bbb aaa ccc aaa", "aaa")

Вывод:

3

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