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

Question

Я написал рекурсивную функцию, чтобы найти нет. экземпляров подстроки в родительской строке. Я веду счет путем объявления / инициализации счетчика как глобальной переменной вне области действия функции. Проблема в том, что это даст мне правильные результаты только при первом запуске функции, потому что после этого count! = 0 для начала. И если он у меня есть внутри функции, то каждый раз, когда он вызывается рекурсивно, он будет установлен в 0.

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

Примечание: я ищу решение специально для функции recursive, у меня есть итеративная функция, которая отлично работает.

РЕДАКТИРОВАТЬ: Спасибо всем, это было частью домашней работы, поэтому я использовал только строковый модуль

Answer 1

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

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)

Answer 2

Ваша рекурсивная функция имеет производительность 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

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

index = find(target, key, start_index)

Answer 3

Еще одно замечание: все представленные решения (от исходного Q до всех As) решают проблему, которая отличается от конкретно заявленной (я полагаю, что это ошибка в формулировке конкретной проблемы, но стоит исправить, если так ;-). Рассмотрим:

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

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

найти нет. случаев подстрока в родительской строке.

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

Так, например:

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, считая оба (перекрывающихся) вхождения.

Answer 4

Вот что-то похожее на ответ Грега Хьюгилла. Однако вместо этого мы передаем текущий счетчик каждый раз, когда вызываем функцию, а затем возвращаем счетчик, когда больше нет совпадений. Хотя я подозреваю, что в Python это не имеет значения, в языках, которые реализуют рекурсию хвостового вызова, это позволяет оптимизировать каждый последующий вызов 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))

Answer 5

Учитывая перекрывающиеся вхождения и поддерживая исходное определение из MIT , это более простой и компактный код, который я могу получить.

код:

from string import *
def countSubStringMatchRecursive(target, key):
    index = find(target, key)
    if index > -1:
        return countSubStringMatchRecursive(target[index + 1:], key) + 1
    return 0


def test(target, key):
    instances = countSubStringMatchRecursive(target, key)
    if instances == 0:
        print "No instance of %r in %r" % (key, target)
    else:
        print "Number of instances of %r in %r: %d" % (key, target, instances)

test("atgacatgcacaagtatgcat","ggcc")
test("atgacatgcacaagtatgcat","atgc")
test("banana", "ana")

выход:

Нет экземпляра 'ggcc' в 'atgacatgcacaagtatgcat'

Количество экземпляров 'atgc' в 'atgacatgcacaagtatgcat': 2

Количество случаев «ана» в «банане»: 2

Answer 6

Я делаю этот курс по OpenCourseware, это здорово. В любом случае, это то, что я сделал. Я черпал вдохновение из Адамса выше.

def countSubStringMatchRecursive(target, key, counter = 0):
    if find(target,key) == 0:
        countSubStringMatchRecursive(target[1:], key, counter + 1)
    elif find(target,key) > 0:
        countSubStringMatchRecursive(target[1:], key, counter)
    elif find(target,key) == -1:
        print counter

Answer 7

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

Answer 8

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

код:

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)

выход:

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

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

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

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

С самого начала строкового модуля (он будет на вашем компьютере как <your Python install directory>/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) - пустая трата времени.

Answer 9

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

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

Answer 10

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

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

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

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