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

Question

Я написал рекурсивную функцию, чтобы найти no. экземпляров подстроки в родительской строке. Способ, которым я поддерживаю подсчет, заключается в объявлении/инициализации count как глобальной переменной вне области действия. Проблема в том, что это даст мне правильные результаты только при первом запуске функции, потому что после этого 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 функции конкретно, я итеративный функция, которая работает нормально.

EDIT: Спасибо всем, это было частью домашней работы, так что я только с помощью строки модуль

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

Другим способом может быть наличие третьего необязательного параметра в функции countSubStringMatchRecursive, называемой счетчиком, изначально установленным на 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 

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

Answer 3

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

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

index = find(target, key, start_index) 

Answer 4

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

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 5

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

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

код:

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, которое будет b е естественно медленнее, чем при использовании target.count(key) ... так что я не беспокоили с фиксируя все проблемы, ваша версия была ... но прочитать PEP-008 :-)

Комментарии струнной модуля

You прокомментировал, что вы опустили 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 7

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

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

первое выражение считая неперекрывающихся вхождения «ана» в «банан»; второй - все вхождения - есть два вхождения во всех, по индексам 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 8

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

Answer 9

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

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 10

Принимая во внимание перекрывающихся вхождений и сохранении исходного определения из 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

Количество экземпляров «ana» в «банане»: 2