Факториал числа

Факториал числа — рекурсивное решение

Факториал (обозначается n!) — это произведение всех положительных целых чисел от 1 до n включительно. Это классическая задача для демонстрации рекурсии.

Математическое определение

n! = n × (n-1) × (n-2) × ... × 1

Специальные случаи:
0! = 1 (по определению)
1! = 1

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

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

• Базовый случай (base case): n = 0 или n = 1, возвращаем 1
• Рекурсивный случай: n! = n × (n-1)!

def factorial(n):
    # Базовый случай
    if n == 0 or n == 1:
        return 1
    # Рекурсивный случай
    return n * factorial(n - 1)

# Примеры использования
print(factorial(5))   # 120 (5 × 4 × 3 × 2 × 1)
print(factorial(0))   # 1
print(factorial(1))   # 1
print(factorial(10))  # 3628800

Как работает рекурсия на примере factorial(5)

factorial(5)
= 5 × factorial(4)
= 5 × (4 × factorial(3))
= 5 × (4 × (3 × factorial(2)))
= 5 × (4 × (3 × (2 × factorial(1))))
= 5 × (4 × (3 × (2 × 1)))
= 5 × (4 × (3 × 2))
= 5 × (4 × 6)
= 5 × 24
= 120

Более компактное решение

def factorial(n):
    return 1 if n <= 1 else n * factorial(n - 1)

print(factorial(5))  # 120

С валидацией ввода

def factorial(n):
    # Проверяем корректность входных данных
    if not isinstance(n, int):
        raise TypeError("Факториал определен только для целых чисел")
    if n < 0:
        raise ValueError("Факториал не определен для отрицательных чисел")
    
    # Базовый случай
    if n <= 1:
        return 1
    # Рекурсивный случай
    return n * factorial(n - 1)

# Тестирование
print(factorial(5))   # 120
print(factorial(0))   # 1

# Обработка ошибок
try:
    print(factorial(-5))  # ValueError
except ValueError as e:
    print(f"Ошибка: {e}")

try:
    print(factorial(3.5))  # TypeError
except TypeError as e:
    print(f"Ошибка: {e}")

Итеративное решение (альтернатива)

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

def factorial(n):
    if n < 0:
        raise ValueError("Факториал не определен для отрицательных чисел")
    
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

print(factorial(5))   # 120
print(factorial(100)) # Работает без проблем

Встроенное решение в Python

import math

print(math.factorial(5))   # 120
print(math.factorial(0))   # 1
print(math.factorial(100)) # Работает для больших чисел

Сравнение подходов

# Рекурсивное решение
def factorial_recursive(n):
    return 1 if n <= 1 else n * factorial_recursive(n - 1)

# Итеративное решение
def factorial_iterative(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

# Встроенное решение
from math import factorial

# Производительность
import time

n = 1000

# Рекурсивное решение упадёт при большом n (RecursionError)
# Python имеет лимит на глубину рекурсии (~1000)
# Итеративное и встроенное работают без проблем

Проблема глубины рекурсии

def factorial_recursive(n):
    return 1 if n <= 1 else n * factorial_recursive(n - 1)

# При n > ~1000 получим RecursionError
try:
    print(factorial_recursive(5000))
except RecursionError as e:
    print(f"Ошибка: {e}")
    print("Превышена максимальная глубина рекурсии")

# Проверить лимит
import sys
print(sys.getrecursionlimit())  # обычно 1000

С мемоизацией (оптимизация рекурсии)

from functools import lru_cache

@lru_cache(maxsize=None)
def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

# Первый вызов вычисляет
print(factorial(100))  # Вычисляется

# Второй вызов берёт из кэша
print(factorial(100))  # Из кэша (быстро)

# Частичный результат используется
print(factorial(105))  # Использует кэш для factorial(100)

Тестирование

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

# Юнит-тесты
assert factorial(0) == 1
assert factorial(1) == 1
assert factorial(5) == 120
assert factorial(10) == 3628800

print("Все тесты пройдены!")

Рекомендации

• Для обучения: используйте рекурсивное решение, чтобы понять концепцию
• Для производства: используйте math.factorial() или итеративное решение
• Для больших чисел: итеративное решение или встроенное
• Для оптимизации рекурсии: применяйте мемоизацию с @lru_cache