Неспособность понять рекурсию

Новый для Python и пытается понять рекурсию. Я пытаюсь создать программу, которая печатает количество раз, когда строка «ключ» находится в строке «target» с использованием рекурсивной функции, как в задаче 1 заданной задачи Intro курса MIT. У меня возникла проблема с попыткой выяснить, как эта функция будет работать. Я прочитал документацию и некоторые учебники по ней, но есть ли у кого-нибудь какие-либо советы о том, как лучше понять рекурсию, чтобы помочь мне исправить этот код?

from string import * def countR(target,key): numb = 0 if target.find(key) == -1: print numb else: numb +=1 return countR(target[find(target,key):],key) countR('ajdkhkfjsfkajslfajlfjsaiflaskfal','a') 

По рекурсии вы хотите разделить проблему на более мелкие проблемы, которые вы можете решить самостоятельно, а затем объединить их решение, чтобы получить окончательное решение.

В вашем случае вы можете разделить задачу на две части: проверка наличия (если) первого появления key и последующего подсчета рекурсивно для остальных.

Есть ли там ключ:
– Нет: возврат 0.
– Да: Удалить key и сказать, что количество клавиш – 1 + номер key в остальном

В коде:

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

Изменить :
Следующий код затем печатает желаемый результат:

 print(countR('ajdkhkfjsfkajslfajlfjsaiflaskfal','a')) 

Рекурсия не работает. numb бесполезен – каждый раз, когда вы вводите рекурсию, numb создается снова как 0, поэтому он может быть только 0 или 1 – никогда не результат, который вы ищете.

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

Кроме того, вам нужно на самом деле продвинуть срез, чтобы строка, которую вы только что нашли, больше не появится.

 from string import * def countR(target,key): if target.find(key) == -1: return 0 else: return 1+countR(target[target.find(key)+len(key):],key) print(countR('ajdkhkfjsfkajslfajlfjsaiflaskfal','a')) 

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

 def factorial(n): """return the factorial of any positive integer n""" if n > 1: return n * factorial(n - 1) else: return 1 # Cheating a little bit by ignoring illegal values of n 

Вышеупомянутая функция демонстрирует то, что я бы назвал «нормальным» видом рекурсии – значение, возвращаемое внутренними фреймами, управляется внешними фреймами.

Ваша функция немного необычна в том, что она:

  1. Не всегда возвращает значение.
  2. Внешние кадры ничего не делают с возвращаемым значением внутренних кадров.

Давайте посмотрим, можем ли мы реорганизовать его, чтобы следовать более традиционному шаблону рекурсии. (Написано как синтаксис спойлера, чтобы вы могли увидеть, можете ли вы получить его самостоятельно, сначала):

def countR (target, key): idx = target.find (key) `if idx> -1: return 1 + countR (target [idx + 1:], key) else: return 0

Здесь countR добавляет 1 каждый раз, когда находит цель, а затем возвращается к оставшейся части строки. Если он не находит совпадение, он все равно возвращает значение, но он выполняет две критические вещи:

  1. При добавлении во внешние рамки не изменяется значение.
  2. Больше не повторяется.

(ОК, так что критические вещи – это то, чего он не делает. Вы получаете картину.)

Meta / Edit: Несмотря на эту мета-статью, по-видимому, невозможно правильно форматировать код в тексте спойлера. Поэтому я оставлю его неформатированным до тех пор, пока эта функция не будет исправлена ​​или навсегда, в зависимости от того, что наступит раньше.

Если ключ не найден в цель, напечатайте numb, иначе создайте новую строку, которая начинается после найденного события (так отрезала начало), и продолжите поиск оттуда.