Рекурсия и подпрограммы

Главное

Рекурсия — способ решения задачи через вызов функции самой себя на меньших данных. Обязательна база рекурсии, иначе вызовы не закончатся.

Правила

1. База рекурсии — условие остановки
2. Рекурсивный шаг сводит задачу к меньшей
3. Любую рекурсию можно заменить циклом, но иногда рекурсия нагляднее
4. Подпрограмма (функция) позволяет переиспользовать код

Разберём пример

Как вычислить факториал рекурсивно?

База: 0! = 1. Шаг: n! = n · (n−1)!. Вызовы идут вниз до базы, затем результаты перемножаются на обратном ходе.

Частые ошибки

• Забывать базу рекурсии и получать бесконечные вызовы
• Путать рекурсию и итерацию по смыслу

Потренироваться

Задания с проверкой и подсказками, схема темы и разбор ошибок с ИИ-репетитором — в уроке на платформе.