Рекурсия

Рекурсия — это приём, когда функция решает задачу, вызывая себя для меньшего подслучая. Обязательны базовый случай (условие остановки) и рекурсивный шаг, приближающий к нему.

Сложность: зависит от задачи; глубина рекурсии расходует стек — O(глубина) памяти. Слишком глубокая рекурсия в Python приводит к RecursionError.

def factorial(n):
    if n <= 1:        # базовый случай
        return 1
    return n * factorial(n - 1)  # рекурсивный шаг

print(factorial(5))  # 120