Открывается в новой вкладке

Мы всегда на связи

Пишите в любое удобное время:
whatsappvktelegramMAX
Или задайте вопрос через форму:

Мы всегда на связи

Заявка принята!

Мы уже получили заявку и скоро свяжемся. Расскажите немного о ребёнке — так быстрее подберём группу (необязательно).

Спасибо!

Мы свяжемся с вами в ближайшее время.

Учебник по информатике и математике

Структурированные пути обучения: от первых программ до олимпиад и вступительных в топ-школы.
    Темы
    Заниматься с наставником
    прочитали
    3 задачи

    Факториал и числа Фибоначчи: рекурсия и цикл

    Оглавление:

    Класс собирается на общее фото, и фотограф хочет поставить в первый ряд пятерых. Сколькими способами их можно расставить? На первое место — любого из пяти, на второе — любого из оставшихся четырех, и так далее: $5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120$ вариантов. Для десяти человек вариантов уже 3 628 800.

    Такое произведение называется факториалом. Факториал и числа Фибоначчи — классические примеры рекурсии: на них видно, когда она удобна, когда опасно медленная и как это исправить.

    Факториал

    Факториал числа $n$ — произведение всех натуральных чисел от 1 до $n$. Его обозначают восклицательным знаком: $n! = 1 \cdot 2 \cdot \ldots \cdot n$. По договоренности $0! = 1$.

    Заметь, что $5! = 5 \cdot 4!$, а $4! = 4 \cdot 3!$. В общем виде $n! = n \cdot (n - 1)!$ — это готовый шаг рекурсии, а базовый случай — $0! = 1! = 1$. Запишем два решения, рекурсивное и через цикл:

    def factorial_rec(n):
        if n <= 1:                       # базовый случай: 0! = 1! = 1
            return 1
        return n * factorial_rec(n - 1)  # шаг: n! = n * (n - 1)!
    
    
    def factorial_loop(n):
        result = 1
        for i in range(2, n + 1):
            result *= i
        return result
    
    
    print(factorial_rec(5))    # 120
    print(factorial_loop(10))  # 3628800
    

    Оба решения работают за $O(n)$: нужно около $n$ умножений. Но рекурсивная версия держит в стеке $n$ ожидающих вызовов, и factorial_rec(1000) упадет с RecursionError — предел глубины в Python около 1000. А factorial_loop(1000) посчитает число из 2568 цифр — целые числа в Python не переполняются.

    Числа Фибоначчи

    Последовательность Фибоначчи начинается с 0 и 1, а каждое следующее число равно сумме двух предыдущих: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55…

    $$F_0 = 0, \quad F_1 = 1, \quad F_n = F_{n-1} + F_{n-2}$$

    Пример из жизни: ты поднимаешься по лестнице, шагая через одну или две ступеньки. Сколькими способами можно подняться на $n$ ступенек? На последнюю ты попадаешь либо с предпоследней, либо со ступеньки ниже нее. Значит, способов столько, сколько для $n - 1$ и $n - 2$ ступенек вместе — это правило Фибоначчи. Для 4 ступенек их $F_5 = 5$.

    Определение переводится в код почти дословно:

    def fib(n):
        if n < 2:  # F(0) = 0, F(1) = 1
            return n
        return fib(n - 1) + fib(n - 2)
    
    
    print(fib(10))  # 55
    print(fib(30))  # 832040
    

    Почему наивная рекурсия медленная

    Функция много раз считает одно и то же: fib(5) вызывает fib(4) и fib(3), но fib(4) снова вызывает fib(3), и так на каждом шаге. Посмотри, как растет число вызовов:

    $n$ Сколько раз вызовется fib
    10 177
    20 21 891
    30 2 692 537
    40 331 160 281

    Когда $n$ растет на единицу, вызовов становится примерно в 1,6 раза больше. Такой рост называют экспоненциальным, и сложность наивного Фибоначчи грубо оценивают как $O(2^n)$. Поэтому fib(30) считается за доли секунды, fib(40) на обычном ноутбуке занимает секунды, а то и десятки секунд, а fib(50) — уже минуты.

    Цикл: быстро и без стека

    Сам ты считал бы иначе: слева направо, помня только два последних числа. Так же работает цикл:

    def fib_loop(n):
        a, b = 0, 1          # F(0) и F(1)
        for _ in range(n):
            a, b = b, a + b  # сдвигаемся на одно число вперед
        return a
    
    
    print(fib_loop(10))   # 55
    print(fib_loop(100))  # 354224848179261915075
    

    Подчеркивание _ — имя для переменной, значение которой не нужно. Цикл делает $n$ шагов, сложность $O(n)$. Сотое число Фибоначчи считается мгновенно, а наивной рекурсии на него понадобилось бы больше ста тысяч лет.

    Мемоизация: рекурсия с памятью

    Рекурсию можно оставить, если запоминать найденные ответы. Этот прием называется мемоизацией (от английского memo — «заметка»). В Python для него есть декоратор lru_cache из модуля functools:

    from functools import lru_cache
    
    
    @lru_cache(maxsize=None)
    def fib(n):
        if n < 2:
            return n
        return fib(n - 1) + fib(n - 2)
    
    
    print(fib(100))  # 354224848179261915075
    

    Строка с @ над функцией — декоратор: он «оборачивает» функцию и запоминает результат для каждого аргумента. Когда fib(3) понадобится второй раз, ответ возьмется из памяти. Теперь каждое число от fib(0) до fib(100) считается один раз, и время падает с $O(2^n)$ до $O(n)$. maxsize=None снимает ограничение на число запомненных ответов.

    Совет: Мемоизация не отменяет предел глубины: fib(5000) с пустым кешем все равно упадет с RecursionError. Для больших $n$ надежнее цикл. А факториал в настоящих программах вручную не пишут: есть готовая функция math.factorial(n).

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

    Частая ошибка: Если у Фибоначчи оставить один базовый случай if n == 0: return 0, вызов fib(1) уйдет в fib(0) и fib(-1). Отрицательные числа никогда не дойдут до нуля, и программа упадет с RecursionError. Проверка n < 2 закрывает оба базовых случая.

    • result = 0 в факториале через цикл: произведение всегда будет нулем, начинать надо с 1.
    • range(2, n) вместо range(2, n + 1): последнее число $n$ не войдет, и получится $(n - 1)!$.

    Проверь себя

    1.

    Сколько всего раз вызовется функция fib (наивная рекурсия) при вычислении fib(4), считая и первый вызов?

    2.

    Сколькими способами можно подняться по лестнице из 6 ступенек, если шагать на одну или на две ступеньки?

    3.

    Соедини строку кода и ее роль.

    @lru_cache(maxsize=None)

    Базовый случай для Фибоначчи

    if n < 2: return n

    Запоминает результаты вызовов

    a, b = b, a + b

    Шаг рекурсии для факториала

    return n * factorial_rec(n - 1)

    Шаг цикла для Фибоначчи

    Поможем подобрать обучение

    Оставьте телефон. Мы перезвоним, поможем выбрать подходящие занятия и ответим на вопросы

    Поможем подобрать обучение

    Заявка принята.

    Мы свяжемся с вами