Рекурсия: практика
Рекурсия подходит, когда задача сводится к такой же, но меньше: число — к числу поменьше, список — к хвосту, поле — к соседним клеткам. Сначала напишите базовый случай, потом — как ответ собирается из ответов маленьких задач.
Если одни и те же вызовы повторяются, запомните ответы в словаре. А если вызовов друг в друге больше нескольких сотен, лучше обычный цикл: глубина рекурсии ограничена.
Наибольший общий делитель по алгоритму Евклида — короткий пример: НОД(a, b) равен НОД(b, a % b), а НОД(a, 0) = a.
def gcd(a, b):
if b == 0:
return a
return gcd(b, a % b)
print(gcd(84, 36))
Итог главы. Рекурсивная функция вызывает саму себя для задачи поменьше и останавливается в базовом случае. Ответ собирают из ответов меньших задач через return.
Рекурсия разбирает числа, строки и списки, перебирает варианты, заливает области на поле. Повторные вызовы ускоряет словарь-память.
В следующей главе — алгоритмы: быстрые сортировки, двоичный поиск, префиксные суммы и два указателя.
Урок пройден
Рекурсия: практика
Выполнено заданий
Очки опыта
Обракоины
Другие уроки по теме
Следующая тема
Рекурсия: практика
Практика главы «Рекурсия»: алгоритм Евклида, Ханойская башня, скобочные записи, разбиения числа, словарь-память. В 6 заданиях вы решите Ханойскую башню, выпишете правильные скобки и разбиения числа, найдете цифровой корень, посчитаете пути Робота и прочитаете программу: что она выведет?