Что такое рекурсия и рекурсивный факториал на Python

Что такое рекурсия? Напишите факториал рекурсивно

Рекурсия — это подход, при котором функция вызывает саму себя для решения меньшей подзадачи. У рекурсивной функции обязательно должно быть базовое условие остановки; факториал определяется как n! = n × (n - 1)!, а 0! = 1.

Подробный ответ

Что такое рекурсия

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

Что такое факториал

Факториал неотрицательного целого числа n — произведение всех целых чисел от 1 до n. По определению 0! = 1.

Рекурсивное решение

def factorial(n: int) -> int:
    if n < 0:
        raise ValueError('Factorial is defined only for non-negative integers')

    if n == 0:
        return 1

    return n * factorial(n - 1)

Пример работы

print(factorial(5))
# 120

# factorial(5)
# 5 * factorial(4)
# 5 * 4 * factorial(3)
# 5 * 4 * 3 * 2 * 1
# 120

Базовый случай

Условие if n == 0: return 1 — базовый случай. Без него функция вызывала бы себя бесконечно, пока Python не завершил бы программу с ошибкой превышения глубины рекурсии.

Сложность

Функция вызывает себя n раз, поэтому временная сложность составляет O(n). Из-за стека рекурсивных вызовов дополнительная память также равна O(n).

Итеративный вариант

def factorial_iterative(n: int) -> int:
    result = 1

    for number in range(2, n + 1):
        result *= number

    return result

Итеративное решение тоже имеет временную сложность O(n), но использует O(1) дополнительной памяти.

Как ответить на собеседовании

Рекурсия — это вызов функцией самой себя для меньшей подзадачи. В рекурсивном решении обязательно нужен базовый случай. Для факториала базой является 0! = 1, а рекурсивный шаг — n * factorial(n - 1). Такое решение работает за O(n) времени и использует O(n) памяти стека.