#python #recursion
Вопрос:
Я изо всех сил пытаюсь понять поведение интерпретатора python, когда дело доходит до рекурсивных функций.
Следующий код не удался и дал неожиданный результат (0,1,2,3,4,5,5,4,5,5,3,4,5….):
def recur(num): while num lt; 6: print(num) num =1 recur(num) recur(0) Выполнение функции возврата решило проблему (1,2,3,4,5)
def recur(num): while num lt; 6: print(num) num =1 return recur(num) recur(0) Имеет смысл, что без возврата исходная функция не завершается при инициализации нового вызова, однако я не могу объяснить поток, который привел к результатам.
Спасибо!
Комментарии:
1.первая итерация создала функцию с 1, вторая сделала 2, третья сделала 3 … это продолжалось до 6, затем функция «выше» переместилась на одну и создала новую функцию … в принципе, ваш первый вызов функции хотел создать 6 различных функций
num[1-6], и каждая новая функция хотела сделать то же самое (но в другом диапазоне)2. Спасибо! Действительно, это была скорее попытка «принудить» рекурсию, вероятно, не лучший метод в этом примере.
Ответ №1:
Добавление возврата внутри while цикла просто гарантирует, что цикл повторится только на одной итерации. Для рекурсии вам на самом деле не нужен цикл (рекурсия-это цикл), который только запутывает ситуацию. Вам нужно условие, которое останавливает рекурсии, и рекурсивный вызов:
def recur(num): if num lt; 6: # base condition print(num) recur(num 1) # recursive call recur(0) С принтами:
0 1 2 3 4 5 Очевидно , что если вы хотите распечатать, начиная с 1 , вы можете позвонить recur(1) .
Ответ №2:
Чтобы объяснить свой первоначальный вывод (0,1,2,3,4,5,5,4,5,5,3,4,5....) :
Первые 6 записей (0,1,2,3,4,5) создаются с помощью начальной рекурсии. Вы печатаете одно значение, а затем выполняете рекурсию со следующим более высоким значением. В 6 ваша рекурсия заканчивается без печати значения (цикл while не вводится).
В этот момент вы возвращаетесь к функции, которая напечатала 5 и теперь удерживает значение 6 (поскольку оно увеличивалось перед повторением). Функция останавливает свой цикл while, возвращает. Затем вы переходите к функции, которая изначально имела номер 4. Его значение было увеличено до 5. Поэтому он зацикливается, печатает 5, увеличивается до 6, затем повторяется. Ничего не делает, возвращается.
Функция, которая первоначально получила 4, теперь находится на 6 и возвращается к функции, которая первоначально получила 3 и теперь удерживает 4. Итак, теперь рекурсия продолжается для 4 и 5, затем полностью возвращается к функции, первоначально получавшей 2, теперь удерживающей 3, и так далее и тому подобное.
Другими словами, если вы отсчитываете только рекурсии, значения создаются в следующих группах: (0,1,2,3,4,5), (5,), (4,5), (3,4,5), ...)
(Примечание: я небрежен в своей терминологии. Когда я говорю «возврат к функции», я имею в виду возврат к кадру стека рекурсивной функции. Надеюсь, я вас больше не смутил).