О пользе рекурсии

Эту заметку о пользе рекурсии я написал после прочтения соответствующей части книги С. Макконнелла «Совершенный код». Книга прекрасная, но, на мой взгляд, автор совершенно напрасно обещает уволить сотрудника, использующего рекурсию. Мне рекурсия помогала много раз, и я видел множество превосходных примеров её использования.

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

Компактность записи

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

Небольшое замечание: для краткости, все мои реализации (и рекурсивные и не рекурсивные) будут достаточно просты. Например, я не буду проверять корректность входных данных (отрицательное число, вообще не число). Вопросов надёжности кода я коснусь чуть ниже.

# пример 1
# вычисление факториала на языке Python без рекурсии
def fac(n):
    f = 1
    i = 2
    while i <= n:
        f *= i
        i += 1
    return f

Многие могут сказать, что функция чрезмерно усложнена добавлением переменной i. Чуть ниже, я поясню, зачем я это сделал, а пока приведу классический вариант:

# пример 2
# Python; без рекурсии; классика
def fac(n):
    f = 1
    while n > 1:
        f *= n
        n -= 1
    return f

У такого подхода есть один важный недостаток, к нему мы скоро вернёмся. А пока давайте посмотрим на рекурсивные реализации.

Сперва классическая реализация с рекурсией, всё на том же Python:

# пример 3
# Python; с рекурсией; классика
def fac(n):
    if n == 0:
        return 1
    else:
        return n * fac(n-1)

Обратите внимание, на сколько близко эта запись перекликается с математическим определение факториала.

Можно сэкономить одну строчку:

# пример 4 (экономичная запись примера 3)
# Python; с рекурсией; классика
def fac(n):
    if n == 0:
         return 1
    return n * fac(n-1)

Ту же самую мысль можно записать ещё компактней

# пример 5 (одно-строчная запись примера 3)
def fac(n): return (1 if n == 0 else n * fac(n-1))

Этот пример работает только в Python 2.5 и старше.

Приведу два примера на Haskell:

-- пример 7
-- запись примера 3 на Haskell
fac n = if n == 0
          then 1
          else n * fac (n-1)

Приведу ещё один, более компактный, но вполне понятный для неподготовленного читателя:

-- пример 8
-- реализация рекурсивного вычисления факториала
-- на Haskell; дополнительно компактности удалось
-- достичь за счёт использования клозов (от clause)
fac 0 = 1
fac n = n * fac (n-1)

Можно приводить ещё множество реализаций вычисления факториала, но мне кажется, что приведённых примеров достаточно, чтобы развеять миф о том, что рекурсивные реализации громоздки.

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

Как же можно повысить понятность кода, используя рекурсию?

Неизменяемость переменных

При программировании бывает полезно придерживаться концепции неизменяемости переменных (многие языки программирования вообще не допускают изменения переменных). Это позволяет убить сразу много зайцев:

• во-первых, вы избавляетесь от сайд-эффектов (side effect) — побочных эффектов, связанных с тем, что одна и та же переменная принимает разные значения в разные моменты времени;
• во-вторых, вы можете легко проверять данные на корректность; это достаточно делать один раз и все проверки можно группировать, скажем, в начале функции; это повышает не только надёжность кода, но и его читабельность, а так же, позволяет ничего не забыть;
• в-третьих, вы существенно повышаете читабельность кода, так как читающему не надо просматривать весь код, чтобы отследить эволюцию переменной; ему достаточно найти то место, где переменной присвоено значение, а дальше он может быть уверен, что это значение не изменится.

Давайте рассмотрим эти аспекты подробней.

Избавление от сайд-эффектов (side effect)

Рассмотрим рекурсивную и не рекурсивную реализацию. Повторю их здесь.

Не рекурсивная (одна из, она мне нравится больше; почему — поясню ниже)

# пример 1
# вычисление факториала на языке Python без рекурсии
def fac(n):
    f = 1
    i = 2
    while i <= n:
        f *= i
        i += 1
    return f

Тут мы видим сразу две изменяемые переменные — f и i. Причём i оказывает влияние на f в одном месте, а изменяет своё значение — в другом. Это потенциальный источник ошибок такого вида:

# пример 1 с ошибкой
def fac(n):
    f = 1
    i = 2
    while i <= n:
        i += 1 # Ошибка
        f *= i # Порядок выполнения операций не верный
    return f

Даже в таком тривиальном коде заметить ошибку не легко. С увеличением объёма кода, находить ошибки, связанные с побочными эффектам, становится очень сложно.

Самое неприятное в таких ошибках то, что компилятор или интерпретатор, в большинстве случаев, ничего не заподозрит; с его точки зрения, код абсолютно правильный. Чтобы найти такую ошибку, вам придётся кропотливо вычитывать весь код (или не менее кропотливо работать в отладчике, или читать километровые файлы детальных протоколов, одно другого не слаще), следя за всеми изменениями переменных, отслеживая множество вариантов развития событий, учитывая возможную много-поточность выполнения операций... Весь этот ад появляется только потому, что переменные в нашей программе изменяемые и одно действие наводит побочный эффект на другое действие.

Вариант с рекурсией полностью избавлен от этого недостатка (приведу его здесь снова):

# пример 3
# Python; с рекурсией; классика
def fac(n):
    if n == 0:
        return 1
    else:
        return n * fac(n-1)

В процессе выполнения функции fac ни одна переменная не изменяется. Это обстоятельство может сильно упростить чтение и понимание кода.

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

Лёгкость проверки корректности значений

Так как значения не изменяются, их можно легко проверять на корректность. Причём все проверки можно группировать, не опасаясь, что переменная изменится к моменту, когда над ней будут производиться какие-то действия.

Строго говоря, проверка становится вполне естественной веткой в существующем алгоритме. Вот модифицированный пример 3:

# пример 3 с проверкой значений на "не-отрицательность"
def fac(n):
    if n == 0:
        return 1
    if n >  0:
        return n * fac(n-1)
    else:
        return 'ERROR'

Чтобы реализовать аналогичную проверку в не рекурсивном варианте кода (примеры 1 и 2), пришлось бы добавить отдельный проверяющий механизм. И это не случайно, причины кроются в различном подходе к работе с данными. К этим различиям я ещё вернусь в секции «"Данные, управляемые программами" против "программ, управляемых данными"».

Однозначность назначения каждой переменной

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

Взгляните ещё раз на рекурсивный пример 3: переменная n сохраняет единственное назначение.

Чтобы идея была понятней, давайте введём ещё одну переменную (конечно же, она тоже будет неизменяемой):

# пример 3 с дополнительно переменной
def fac(n):
    if n == 0:
        f = 1
    else:
        f = n * fac(n-1)
    return f

Теперь переменных две и их смысл одинаков везде, где они используются: n — аргумент, f — факториал n (и ни что иное).

Теперь пришло время объяснить, почему мне так не симпатичен пример 2 (приведу его здесь снова):

# пример 2
# Python; без рекурсии; классика
def fac(n):
    f = 1        # первое использование f
    while n > 1:
        f *= n   # второе использование f
        n -= 1
    return f     # третье использование f

Здесь переменная f используется трижды, и все три раза она имеет разный смысл:

• первый раз — начальное значение — фиксированная константа;
• второй раз она используется как аккумулятор для хранения промежуточных результатов;
• трети раз — это искомое значение — факториал n.

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

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

И снова, источник всех бед только то, что переменная f — изменяемая.

«Данные, управляемые программами» против «программ, управляемых данными»

Существует два подхода к обработке данных, имеющих фундаментальные различия.

Первый — «программа управляет данными». Это наиболее простой и общеизвестный способ взаимодействия с данными. Если данные просты, то он позволяет без труда обрабатывать их, но если данные сложны (например, это некие конструкции, допускающие многократные вложения: HTML, XML, PostScript или просто программа на некотором языке высокого уровня), то алгоритму приходится обрабатывать множество возможных вариантов. Одна из наибольших проблем — обработка ошибок. Чтобы точно диагностировать ошибку, приходится рассматривать множество вариантов во множестве мест кода. Группировка проверок может значительно помочь программисту, но такой подход таит потенциальную опасность того, что значение изменится где-то между проверкой его корректности и его использованием.

Создавая такой код, очень легко что-то упустить и создать «дырку» — такой код, который будет работать непредусмотренным образом, если получит непредусмотренные автором данные. То есть злоумышленник сможет скомбинировать такие входные данные, которые заставят код работать не так, как задумывал автор.

Второй подход — «данные управляют программой». Этот подход используется в функциональных языках программирования и наиболее чисто реализован (на мой взгляд) в XSLT.

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

Давайте я приведу чуть-модифицированный вариант третьего примера:

# пример 3 (чуть модифицированный)
def fac(n):
    if n == 0: return 1
    if n != 0: return n * fac(n-1)

Такая запись делает более очевидным тот факт, что функция fac не кодирует никакого алгоритма; она не определяет последовательность действий. В ней записано два утверждения:

если n равно нулю, то результат -- 1
если n не равно нуля, то результат -- выражение

Эти строки можно выполнять в любом порядке. Для программиста не важно в каком порядке они будут отрабатываться. Он может отладить каждую ветку отдельно, а потом объединить их, не опасаясь сайд-эффектов. То, какая именно ветка будет работать, определятся входными данными. Поэтому подход и называется «данные управляют программой».

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

Рекурсия расточительна

Это правда. Очень существенным недостатком рекурсии, является её расточительность.

Но думая о производительности, всегда следует помнить, что обычно, процедуры, вызываемые часто и принимающие на себя большую нагрузку, составляют не большую часть программы. Остальные части могут быть спроектированы, жертвуя производительностью в пользу облегчения сопровождения и модификации и повышения надёжности кода.

Приведу один пример. Допустим вы разрабатываете программу-архиватор. Понятно, что процедура архивирования должна работать максимально быстро, чтобы не заставлять пользователя ждать. Но так же ясно, что пользователь не будет генерировать тысячи кликов мышкой или нажатий клавиш в секунду, разрешение экрана, скорее всего, не превысит миллион на миллион пикселей, а объём параметров командной строки не будет измеряться мегабайтами. То есть, для части кода, отвечающей за интерфейс, производительность не так существенна.

С другой стороны, алгоритм архивирования вряд ли изменится, и если он написан хорошо, то его доработка и развитие не понадобится. Этого нельзя сказать об интерфейсе, здесь совершенству нет предела. В таком случае, код, описывающий интерфейс, должен быть понятным, простым и легко наращиваться.

Любая программа (и комплексы программ тоже) имеет не так уж много мест, в которых оптимизация действительно нужна. В большинстве же случаев, оптимизация не даёт выигрыша в производительности, но затрудняет дальнейшее развитие программы.

Учитывая это обстоятельство, можно достаточно смело говорить о том, что использование рекурсии противопоказано лишь в немногих случаях. А в большинстве случаев использование рекурсии вполне допустимо, и при разумном применении, рекурсия может сослужить хорошую службу.

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

def fac(n, a=None):
    if a is None:
        a = 1
    if n < 2:
        return a
    return fac(n - 1, a * n)

Мы мало что изменили. Фактически, мы просто поменяли порядок умножения. Но теперь мы получили вычисление факториала с хвостовой рекурсией.

Она характерна тем, что после рекурсивного вызова не выполняется никаких действий (наш предыдущий вариант таким свойством не обладал). В этом случае компилятор может превратить рекурсию в цикл. В gcc это сделает уже -O2-оптимизация. То есть, мы получили рекурсию без дополнительных накладных расходов.

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

Итого

Рекурсия позволяет создавать код с неизменяемыми переменными, что

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

В некоторых случаях, рекурсия позволяет более ясно сформулировать идею алгоритма; например, это относится к алгоритму быстрой сортировки — quicksort — который рекурсивен по своей природе.

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

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

В любом случае, существует множество языков, в которых рекурсия — единственное средство, для выполнения многих действий. К таким языкам относятся не только «экзотические» функциональные языки, такие как Haskell, но и средства более широкого применения: XSLT-процессоры, макро-процессор m4 (основа системы autoconf и многих систем конфигурирования), и другие средства. Такое «тяготение» к рекурсии — не следствие ограниченности этих языков; напротив, эти языки специально оптимизированы для использования рекурсии; они активно эксплуатируют факт неизменяемости переменных и способны выполнить множество оптимизаций, избавляя программиста от многих забот.