Рекурсия: функция, которая вызывает саму себя

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

Краткий ответ

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

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

У рекурсивного решения всегда должны быть две части:

1. Базовый случай, где функция больше не вызывает себя. 2. Рекурсивный шаг, где задача уменьшается.

Пример с факториалом

Факториал числа n — это произведение чисел от 1 до n.

def factorial(n):
    if n == 0:
        return 1

    return n * factorial(n - 1)

print(factorial(5))

Базовый случай — n == 0. Без него функция вызывала бы себя бесконечно.

Как читать рекурсию

Не пытайтесь раскрывать сразу все вызовы в голове. Сначала проверьте базовый случай. Затем убедитесь, что каждый шаг приближает к нему. После этого разберите маленький пример: factorial(3) вызывает factorial(2), затем factorial(1), затем factorial(0).

Рекурсия и циклы

Многие рекурсивные задачи можно решить циклом. Например, сумму чисел от 1 до n проще записать через for. Рекурсия полезнее там, где структура задачи сама разветвляется: дерево вариантов, обход файлов, перебор ходов, разбор выражения.

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

Главная ошибка — забыть базовый случай или не уменьшать задачу. Вторая ошибка — использовать рекурсию там, где обычный цикл проще и надежнее. В Python есть ограничение глубины рекурсии, поэтому очень длинные цепочки вызовов лучше решать циклом.

Для школьника рекурсия важна не только как прием кодирования. Она учит видеть задачу через повторяющуюся структуру: решить маленькую часть и передать похожую работу следующему вызову.

Что важно запомнить

• Рекурсия возникает, когда функция вызывает саму себя для решения похожей, но более простой задачи.
• В школьной информатике рекурсия встречается в задачах на исполнителей, деревья вариантов, перебор, факториал и анализ программ.
• У рекурсивного решения всегда должны быть две части: Базовый случай, где функция больше не вызывает себя.
• Рекурсивный шаг, где задача уменьшается.

https://yadro-code.ru/lessons/without-university/school-programming-basics/school-programming-19