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

Я написал рекурсивную функцию, чтобы найти 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: Спасибо всем, это было частью домашней работы, поэтому я использовал только строковый модуль

Ответ 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)

Ответ 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)

Ответ 3

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

Ответ 4

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

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

первое выражение подсчитывает неперекрывающиеся вхождения 'ana' в 'banana'; второй - подсчет всех вхождений - есть два вхождения во всех, по индексам 1 и 3 в "банане", и они перекрываются. Поэтому, учитывая оператор проблемы, я цитирую:

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

без упоминания о "неперекрывающемся", кажется, что необходимо учитывать совпадающие вхождения. Конечно, это легко исправить, как только вы заметили - вам просто нужно продвигаться на 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, подсчитывая оба (перекрывающиеся) вхождения.

Ответ 5

Я делаю этот курс на 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

Ответ 6

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

Ответ 7

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

Ответ 8

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

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")

Вывод:

Ответ 9

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

код:

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) является отходами.

Ответ 10

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

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

Ответ 11

steps = 0
def addPersistence(number, steps):
    steps += 1
    if len(str(number))==1:
        print(str(number) + "\nDone---------------------------------------------------")
        print("TOTAL STEPS " + str(steps-1))

    digits = [int(i) for i in str(number)]

    result = 0
    for j in digits:
        result += j


    if len(str(number)) != 1:
        print(number)
        addPersistence(result, steps)

Это пример, скопированный из одного из моих проектов. Эта функция предназначена для добавления к постоянству числа (который добавляет цифры числа и повторяет его до тех пор, пока число не становится равным 1), но, безусловно, его можно использовать повторно, и вы можете использовать свою функцию следующим образом (это код Python 3)., если вы хотите изменить его на Python 2, он все равно будет работать):

count=0
def countSubStringMatchRecursive(target,key,count):
    index=find(target,key)
    targetstring=target
    if index>=0:
        count+=1
        target=target[index+len(key):]
        countSubStringMatchRecursive(target,key,count)
    else :
        pass
    print("STEPS: "+str(count))

Вы можете заметить, что мой код немного отличается. Почему? Ответ заключается в том, что количество шагов, которое требуется для того, чтобы число достигло 1 с помощью этой функции, заключается в том, что последний вызов не включен в мою функцию, поскольку это дублирование вызова перед этим.