Рекурсия на примере факториала

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

Идея факториала

Факториал числа n — это произведение всех чисел от 1 до n. Ключ в том, что факториал n равен n, умноженному на факториал (n-1). То есть задача выражается через себя же, но меньшего размера — идеальный случай для рекурсии.

Базовый случай — обязателен

Чтобы рекурсия не ушла в бесконечность, нужен базовый случай — момент, когда функция даёт ответ без нового вызова. Для факториала это 1: факториал единицы равен 1, дальше углубляться некуда.

def factorial(n):
    if n <= 1:        # базовый случай
        return 1
    return n * factorial(n - 1)

print(factorial(5))   # 120

Как это работает по шагам

factorial(5) ждёт factorial(4), тот — factorial(3) и так до 1. Дойдя до базового случая, вызовы начинают возвращать результаты обратно, перемножаясь: 1, 2, 6, 24, 120. Понимание этого «спуска и подъёма» — суть рекурсии.

Частые вопросы

Что будет без базового случая? Бесконечные вызовы и ошибка переполнения — программа упадёт.

Можно ли факториал без рекурсии? Да, обычным циклом for — часто это даже проще.