Рекурсивный питон - подсчет гласных в строке
Следующий код от гиков для гиков — связь Когда я выполнил визуализацию кода построчно на pythontutor.com, я понял, что n уменьшается до 1 путем рекурсии функции countVowels(). Однако я не понимаю, как n снова увеличивается за счет рекурсии функции isVowel().
P2 — я также не понимаю, почему шаг 27 в pythontutor возвращается к isVowel() и увеличивает n до 2, когда эта строка уже была выполнена для n = 1. Я имею в виду, что она должна напрямую перейти к следующей функции возврата (return(countVowels(str, n-1) + isVowel(str[n-1]))
Пожалуйста, помогите мне.
def isVowel(ch):
return ch.upper() in ['A', 'E', 'I', 'O', 'U']
#count no of vowels from 0 to n
def countVowels(str, n):
if (n==1):
return isVowel(str[n-1])
return(countVowels(str, n-1) + isVowel(str[n-1]))
str = 'abc de'
print(str[0])
print(countVowels(str, len(str)))
Ответы 1
Посмотрите, как оцениваются эти функции:
countVowels("abc", 3) = countVowels("abc", 2) + isVowel("abc"[2])
= (countVowels("abc", 1) + isVowel("abc"[1])) + isVowel("abc"[2])
= ((isVowel("abc"[0])) + isVowel("abc"[1])) + isVowel("abc"[2])
= ((True) + False) + False
= 1
Рекурсивные вызовы countVowels должны быть разрешены первыми, прежде чем isVowel() когда-либо будет оцениваться, потому что Python оценивает выражения слева направо и изнутри наружу (например, в случае вложенных выражений, таких как (x + 1)**2).
поэтому, когда countVowels рекурсивно, в то же время isVowel продолжает расширяться, но выполняется только один раз n == 1, верно? @ddejohn
Не думайте об этом как об одном случае n == 1, а скорее о том, что рекурсивных вызовов больше нет. Базовый случай достигается, когда n == 1 приводит к единственному вызову isVowel, который немедленно возвращает результат. В скобках, которые я добавил, показаны различные «фреймы стека», в которых выполняются эти операции.
Как только этот базовый случай достигнут и вызывается isVowel() (без рекурсивного вызова countVowels(), этот последний кадр стека может быть удален сборщиком мусора, а его результат возвращается предыдущему вызывающему объекту, который затем может оценить вызов это для isVowel() и так далее, и так далее. стек вызовов.
Я бы рекомендовал научиться отслеживать функции с помощью ручки и бумаги, рисовать кадры стека для каждого вызова функции, их локальные переменные и то, как вещи распространяются вверх и вниз по стеку вызовов.
спасибо, я понял эту часть, не могли бы вы также помочь мне со второй частью, функция возврата для n == 1 выполняется дважды, я не понимаю эту часть
Хм? Что ты имеешь в виду? countVowels() вызывается с n == 1, а затем, поскольку это базовый случай, isVowel вызывается с n == 1. Это то, что ты имеешь в виду?
Да, я визуализирую это на pythontutor.com и не понимаю, как выполняются шаги 26, 27, когда они уже выполнены на шаге 22.
Большое спасибо! Я решил это с ручкой и бумагой и получил это @ddejohn
Каждый вызов «countVowels» имеет свое собственное «n». После того, как функция была рекурсивно вызвана с "n==1", она возвращается к вызывающему вызову с "n==2".