Возврат нескольких значений и рекурсия на пальцах

Функция «найди минимум и максимум» естественно считает оба сразу — а вернуть по правилам прошлого занятия может только одно. Приходится либо писать две функции, каждая из которых проходит список заново, либо…

def extremes(values):
    low = values[0]
    high = values[0]
    for x in values:
        if x < low:
            low = x
        if x > high:
            high = x
    return low, high        # два значения через запятую


low, high = extremes(a)     # и принимаем тоже два
print(low, high)

Через запятую можно вернуть сколько угодно значений — главное, чтобы при приёме имён было столько же.

На самом деле return low, high возвращает одно значение — пару, которая в Python называется кортежем. Но пользоваться этим знанием пока не придётся: достаточно помнить, что справа и слева от знака равенства должно быть одинаковое количество имён.

Кстати, приём знакомый. Обмен значениями a, b = b, a, который встречался раньше, устроен ровно так же.

Факториал определяется через самого себя: факториал $n$ — это $n$, умноженное на факториал $n - 1$. Так его и можно записать.

def factorial(value):
    if value <= 1:
        return 1                       # база: дальше не спускаемся
    return value * factorial(value - 1)  # шаг: задача поменьше

Функция, вызывающая саму себя, называется рекурсивной. Устроена она всегда из двух частей, и обе обязательны:

• база — случай, который решается сразу, без вызова себя;
• шаг — сведение задачи к такой же, но меньшей.

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

Читать такое поначалу непривычно. Помогает не пытаться проследить все вызовы в голове, а поверить в два утверждения: «для единицы работает» и «если работает для $n-1$, то работает и для $n$». Этого достаточно.

def digit_sum(value):
    if value < 10:
        return value
    return value % 10 + digit_sum(value // 10)

Последняя цифра плюс сумма цифр всего остального — определение, переписанное кодом почти дословно.

def total(value):
    return value + total(value - 1)

Что произойдёт при вызове total(5)?

Каждый незавершённый вызов занимает место в памяти: пока factorial(5) ждёт результат от factorial(4), оба существуют одновременно.

Поэтому глубина ограничена. В Python — около тысячи вложенных вызовов, дальше программа останавливается с ошибкой RecursionError.

def total(value):
    if value == 1:
        return 1
    return value + total(value - 1)


print(total(900))      # работает
print(total(100000))   # RecursionError

Это не редкость и не экзотика: «сумма чисел до миллиона» рекурсией просто не считается. Отсюда практическое правило:

Если рекурсия уменьшает аргумент на единицу, она годится примерно до тысячи. Если делит пополам — глубина получается около шестидесяти даже для гигантских чисел, и всё в порядке.

Второй случай — самый ценный. Возведение в степень: чтобы вычислить $a^b$, достаточно вычислить $a^{b/2}$ и возвести в квадрат.

def power(base, exp, mod):
    if exp == 0:
        return 1 % mod
    half = power(base, exp // 2, mod)
    result = half * half % mod
    if exp % 2 == 1:
        result = result * base % mod
    return result

Показатель в миллиард миллиардов — шестьдесят вызовов. Цикл сделал бы столько же шагов, но здесь рекурсия честно короче и понятнее.

Числа Фибоначчи определяются через себя, и напрашивается записать это дословно:

def fib(n):
    if n <= 2:
        return 1
    return fib(n - 1) + fib(n - 2)      # выглядит красиво

Работает. Но fib(50) вы не дождётесь.

Причина не в глубине — она всего пятьдесят. Причина в количестве вызовов: каждый вызов порождает два, те ещё по два, и всего их получается больше, чем самих чисел Фибоначчи. Для сорокового числа — около двухсот миллионов вызовов, для девяностого — больше, чем секунд в возрасте Вселенной.

И дело даже не в скорости: одно и то же вычисляется заново десятки миллионов раз. fib(10) в этом дереве встречается тысячи раз, и каждый раз считается с нуля.

Для чисел Фибоначчи есть простой выход — считать по порядку, храня два последних:

a, b = 1, 1
for _ in range(n - 2):
    a, b = b, a + b

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

Функция вычисляет $a^b$, каждый раз уменьшая показатель вдвое.

Примерно какой глубины будет рекурсия при $b$ около миллиона? Введите целое число — количество вложенных вызовов, округлив до целого.

Нет базы. Функция вызывает себя всегда, и программа падает с RecursionError. Признак очевидный, лечение тоже: добавить случай, который решается сразу.

База есть, но до неё не доходит. Аргумент не уменьшается или уменьшается не в ту сторону. Проверяйте: каждый вызов должен быть ближе к базе, чем предыдущий.

Разное количество значений при возврате и приёме. low, high = f(), где функция возвращает одно значение или три. Признак: ValueError про распаковку.

Как проверять себя

• самый маленький аргумент — 0 или 1: именно на нём проверяется база;
• посчитайте глубину: если аргумент уменьшается на единицу, она равна самому аргументу;
• посчитайте количество вызовов: если в шаге два вызова себя, их будет катастрофически много;
• проверьте вручную на трёх: рекурсию проще проследить на маленьком примере, чем на большом.

Лестница прежняя: пять разминочных, семь основных, три со звёздочкой. Зачёт при десяти решённых.

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

В двух задачах рекурсия по определению не подойдёт — это числа Фибоначчи и пути по сетке при больших размерах. Ограничения подсказывают, когда так: если задача решается за секунду только при маленьких числах, посмотрите, не считается ли одно и то же по многу раз.

Задача: «вычислите $n$-е число Фибоначчи, $n$ до 90».

Ученик написал:

def fib(n):
    if n <= 2:
        return 1
    return fib(n - 1) + fib(n - 2)


n = int(input())
print(fib(n))

На маленьких тестах программа отвечает верно, на больших получает превышение времени. Ученик считает, что дело в глубине рекурсии, и хочет её увеличить.

Объясните, в чём он не прав, откуда берётся такое количество работы, и как решить задачу.