База, шаг и доказательство рекурсии

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

Как думаешь, что здесь достаточно проверить

def summa(a, i):
    if i == len(a):
        return 0
    return a[i] + summa(a, i + 1)

Прогонять её на примерах незачем. Достаточно двух проверок:

• при i = len(a) возвращается 0, и сумма пустого хвоста действительно ноль;
• если summa(a, i+1) верно возвращает сумму хвоста от i+1, то a[i] + summa(a, i+1) - сумма хвоста от i.

Это индукция, идущая вниз по убыванию len(a) - i. Она же даёт и завершаемость: len(a) - i строго убывает и неотрицательно, то есть это мера из прошлой главы.

Контракт рекурсивной функции

Приём, который экономит больше всего времени, звучит так: сформулируй, что функция обещает, и пользуйся обещанием, не заглядывая внутрь. Внутри тела рекурсивный вызов надо читать как «здесь кто-то другой уже сделал работу правильно», а не как «здесь начинается ещё один такой же цикл».

Контракт для summa: «возвращает сумму элементов a с индекса i до конца». Всё, что нужно от вызова summa(a, i+1), - выполнение этого контракта. Пытаться проследить вызовы вглубь бессмысленно: на глубине пять человек теряет нить, а доказательство от этого не меняется.

Три обязательные части рекурсии, и они те же, что у индукции:

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

Разбор: почему падает рекурсия без базы

def stepen(a, n):
    return a * stepen(a, n - 1)

Мера n убывает, но снизу не ограничена: при n = 0 вызов уходит в -1, потом в -2. Программа падает не потому, что «рекурсия плохая», а потому, что нарушено условие ограниченности меры. Правильная база - n == 0, и она же задаёт ответ 1.

Вторая типичная поломка тоньше:

def poisk(a, x, levo, pravo):
    s = (levo + pravo) // 2
    if a[s] == x:
        return s
    if a[s] < x:
        return poisk(a, x, s, pravo)
    return poisk(a, x, levo, s)

База есть, мера pravo - levo вроде бы убывает - но в первой ветви s может совпасть с levo, и отрезок не сократится. Это тот же дефект, что был в задаче прошлой главы, и он не зависит от того, цикл перед нами или рекурсия.

Разбор: рекурсия по двум ветвям

def hanoi(n, otkuda, kuda, cherez):
    if n == 0:
        return
    hanoi(n - 1, otkuda, cherez, kuda)
    print(otkuda, kuda)
    hanoi(n - 1, cherez, kuda, otkuda)

Контракт: «переносит башню из n дисков со стержня otkuda на стержень kuda, пользуясь cherez, не кладя больший диск на меньший».

База. Ноль дисков - переносить нечего, контракт выполнен пусто.

Шаг. Верхние n-1 дисков по контракту переезжают на вспомогательный стержень; при этом самый большой диск лежит внизу и никому не мешает - он больше всех, значит никакое перекладывание поверх него правил не нарушит. Дальше самый большой переезжает на место, и снова по контракту башня из n-1 дисков переносится сверху.

Мера. n убывает на единицу и ограничена нулём.

Сколько будет ходов? Обозначим их число T(n). Из кода видно, что T(0) = 0 и T(n) = 2·T(n-1) + 1. Подставляя, получаем 0, 1, 3, 7, 15 - это 2ⁿ - 1, и доказывается это той же индукцией: 2·(2^(n-1) - 1) + 1 = 2ⁿ - 1. Меньше ходов не бывает, потому что самый большой диск обязан переехать хотя бы раз, а перед этим все остальные обязаны собраться на одном стержне.

Что даёт «одна лишняя проверка»

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

def obhod(uzel):
    if uzel is None:
        return
    obhod(uzel.levyj)
    obhod(uzel.pravyj)

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

Теперь сам

Функция должна возвращать True, если строка - палиндром. Сформулируй контракт, базу, шаг и меру.

def palindrom(s, levo, pravo):
    ...