Python. Вывод рекурсивных функций. Какая-то проблема в условии?
Доброго дня! Около недели назад в первый раз начал изучать Python, и передо мной встала задачка, по выводу рекурсивной функции (Скрин).
- Первые два значения вышли нормально, далее "RecursionError".
- Я увеличил лимит, после чего перестала выпадать ошибка, но и результата программа далее так и не выдаёт. Программа будто решила, что она сделала всю работу и завершила расчёт. Какая-то проблема в условии? Или?
Спасибо!
ПрограммированиеPython
МаксPython Q
· 1,0 K
Ваша программа нарушает, наверное, все негласные правила написания рекурсивных функций, какие существуют. Их, правда, не так много:
- Обязательно должно быть условие гарантированной остановки;
- Рекурсивный вызов должен стремиться приблизиться к условию остановки;
- Если возможно, нужно пользоваться хвостовой рекурсией.
У вас же условие `c==0` приводит к новому рекурсивному вызову, условие `b==0` возвращает увеличенное значение второго аргумента, а хвостовой рекурсии нет и быть не может, потому что рекурсивных вызовов на самом деле два.
Я добавил печать простейшей отладочной информации на первую строчку вашего кода, вот так:
def a(b, c):
print("a({b}, {c})".format(b=b, c=c))
if b == 0:
return c + 1
elif c == 0:
return a(b - 1, 1)
else:
return a(b - 1, a(b, c - 1))После того, как я запустил `a(2, 2)`, я увидел вот это:
Посмотрите, сколько дополнительных действий выполняет ваша функция, прежде чем прийти, наконец, к результату. Обратите внимание на то, что в определённые моменты функция начинает отсчитывать в обратную сторону: не вниз (2, 1, 0), а вверх (1, 2, 3….).
Обычно, когда кто-то проектирует рекурсивную функцию, это делается с определённой целью. Никто в реальном промышленном коде не делает рекурсию просто так, чтобы поиграться. Это значит, что динамика рекурсивного процесса ожидается вполне определённой. Ряды должны сходиться, а не расходиться.
После того, как я запустил `a(3, 3)`, я получил такой огромный вывод, что Jupyter Notebooks выгрузил его в текстовый файл. Посмотрите, какие номера последних строк в этом файле. Ну, и на расходящийся ряд опять.
Я объясняю это к тому, что проблема не в питоне, который честно пытается выполнить ваш код, а в организации самого вашего кода. Давайте я перепишу одну строчку, чтобы вам было более понятно, какой на самом деле процесс происходит у вас в общем случае:
def a(b, c):
print("a({b}, {c})".format(b=b, c=c))
if b == 0:
return c + 1
elif c == 0:
return a(b - 1, 1)
else:
first = a(b, c - 1)
second = a(b - 1, first)
return secondСтановится очевидным, что так как у вас есть `return c+1`, то для вычисления `second` может произвестись вызов `a` с увеличенным вторым аргументом. Мало того, что этот код жрёт стек вызовов вдвое быстрее обычной рекурсивной функции, он большую часть времени ещё и тратит на движение в обратную сторону от своего условия остановки.
В качестве хака попробуйте добавить мемоизацию - очень много вызовов с повторяющимися значениями аргументов. Возможно, это вам радикально поднимет производительность (ценой увеличения расхода памяти).
1 эксперт согласен
Переполнение стека, stack overflow. Каждый вызов функции помещается на верх стека, после выполнения, снимается. Стек у вашей программы ограничен.
Когда функция бесконечно вызывает саму себя, если вызовов слишком много, происходит ошибка переполнения стека.
Программа не решила, что сделала всю работу, вы каким-то образом запретили ей выдавать ошибку переполнения... Читать далее