Как исправить рекурсию

Время прочтения
4 мин

Просмотры 18K

Привет, Хабр! Представляю вашему вниманию перевод статьи «Removing a recursion in Python, part 1» автора Эрика Липперта (Eric Lippert).

На протяжении последних 20 лет я восхищался простоте и возможностям Python, хотя на самом деле никогда не работал с ним и не изучал подробно.

В последнее время я присмотрелся к нему поближе — и он оказался действительно приятным языком.

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

• Игрок находится в произвольной клетке на пронумерованном поле;
• Цель вернуться в клетку №1;
• Если игрок находится на чётной клетке, он платит одну монету и проходит половину пути к клетке №1;
• Если игрок находится на нечётной клетке, он может заплатить 5 монет и сразу перейти на первую клетку или заплатить одну монету и сделать один шаг к клетке №1 — на чётную клетку.

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

Задача имеет очевидное рекурсивное решение:

def cost(s):
  if s <= 1:
    return 0
  if s % 2 == 0:
    return 1 + cost(s // 2) 
  return min(1 + cost(s - 1), 5)

Однако эта программа падала, достигая максимальной глубины рекурсии, вероятнее всего из-за того, что автор вопроса экспериментировал с очень большими числами.
Следовательно возникает вопрос: как превратить рекурсивный алгоритм в итерационный на Python?

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

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

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

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

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

Для начала давайте посмотрим как привести программу к такой форме.

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

def add_one(n):
  return n + 1

def get_min(n):
  return min(n + 1, 5)

def cost(s):
  if s <= 1:
    return 0

  if s % 2 == 0:
    argument = s // 2
    result = cost(argument)
    return add_one(result)

  argument = s - 1
  result = cost(argument)
  return get_min(result)

Вторым шагом я хочу вынести вычисление аргумента в отдельную функцию:

# ...
def get_argument(s):
  if s % 2 == 0:
    return s // 2
  return s - 1

def cost(s):
  if s <= 1:
    return 0

  argument = get_argument(s)
  result = cost(argument)

  if s % 2 == 0:
    return add_one(result) 
  return get_min(result)

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

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

#...
def get_after(s):
  if s % 2 == 0:
    return add_one
  return get_min

def cost(s):
  if s <= 1:
    return 0

  argument = get_argument(s)
  after = get_after(s) # after это функция!
  result = cost(argument)
  return after(result) 

Теперь запишем это в более общей и краткой форме:

#...
def is_base_case(s):
  return s <= 1

def base_case_value(s):
  return 0

def cost(s):
  if is_base_case(s):
    return base_case_value(s)

  argument = get_argument(s)
  after = get_after(s)
  return after(cost(argument)) 

Видно, что каждое проделанное изменение сохраняло смысл программы.

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

Если мы захотим, то можем решить эту проблему объединив две вспомогательные функции в одну, возвращающую кортеж.

Но давайте не будем беспокоиться об этом в рамках решения этой задачи.

Мы свели наш рекурсивный метод до максимально общей формы.

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

Кое-что важное на что необходимо обратить внимание на этом шаге — это то, что after не должен сам содержать вызовов cost.

Способ, который я показываю здесь, удаляет единственный рекурсивный вызов.

Если у вас 2 и более рекурсии, то нам понадобится другое решение.

Как только мы привели наш рекурсивный алгоритм к такой форме, преобразовать его в итеративный уже просто.

Хитрость в том, чтобы представить, что происходит в рекурсивной программе.

Как мы делаем рекурсивный спуск: мы вызываем get_argument перед рекурсивным вызовом и вызываем функцию after после возврата из рекурсии.

То есть, все вызовы get_argument происходят перед всеми вызовами after.
Поэтому мы можем преобразовать это в 2 цикла: первый вызывает get_argument и формирует список функций after, а второй вызывает все функции after:

#...
def cost(s):
  # Создаём стек из функций "after". Все эти функции
  # принимают результат рекурсивного вызова и возвращают
  # значение, которое вычисляет рекурсивный метод.
  afters = [ ]
  while not is_base_case(s):
    argument = get_argument(s)
    after = get_after(s)
    afters.append(after)
    s = argument
  # Теперь у нас есть стек функций "after" :
  result = base_case_value(s)
  while len(afters) != 0:
    after = afters.pop()
    result = after(result)
  return result

Больше никакой рекурсии!

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

Этот пример отражает мысль, которую я часто повторяю о стеке вызовов: его цель сообщить то, что произойдёт дальше, а не то, что уже произошло!

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

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

В следующий раз мы рассмотрим более сложный способ удаления рекурсии на Python.

В ходе изучения третьего урока по «Основам Программирования» попался пример на рекурсию. Нужно было вывести на экран последовательность чисел от 1 до 10. Здесь всё понятно: входящее значение проверяется на услови, и если «истина» — печатается число. Затем функция вызывает саму себя заново уже с новым значением (n+1).

В итоге получаем результат: 1 2 3 4 5 6 7 8 9 10

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

А результат получился таким: 11 10 9 8 7 6 5 4 3 2 1

Мало того, что напечаталась ещё и цифра 11, так вся последовательность вывелась в обратном порядке. Но самое главное — почему оно вообще печатается? Ведь при беглом взгляде на код представляется, что этого не должно быть! 10 раз оно проверялось на условие и функция запускала саму себя заново. По идее до команды вывода на печать дело не должно доходить, ведь она стоит после вызова. Только когда значение стало 11, тогда уже вызова нет, и доходит очередь до печати. И после того, как выполнена команда на печать, функция должна завершиться! Ведь после команды на печать уже нет других команд. Но реально печатается ещё 10 значений!

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

Почему я это делаю, зачем мне это надо?

Главная причина — в учебных материалах часто бывает, что теряешься и путаешься. И когда удаётся разобраться, то всегда появляется огромное желание с кем-то поделиться. Не зря ведь говорят, что когда рассказываешь, то сам ещё лучше усваиваешь. Ещё одна причина — на дворе веб 2.0! И содержание сайтов часто формируют сами пользователи. Яркий пример — Википедия. Ну и последняя — очень удобно, когда, например, в гугле можно найти разные варианты рассмотрения той или иной темы. Можно выбрать то, что тебе больше подходит. Пускай данная статья также выступает в качестве одного из вариантов объяснения рекурсии.

Кому это может быть интересно?

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

3 примера, 3 знания

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

Пример 1. Первое просветление. Незаконченная операция и стек. Матрешка

Код примера приведен ниже и должен напечатать сумму чисел от 1 до 5:

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

Рассмотрим по шагам, что происходит в этой программе.

Шаг 1

В строке 16 происходит вызов функции pow. Происходит он через вызов другой команды — alert — всем нам известной команды вывода на печать. Запускается команда alert, а в качестве её значения в параметрах задаётся вызов функции pow. В параметрах вызова функции pow указывается значение 5. Можно ещё называть его стартовым, исходным значением. Таким образом, первая команда, которая исполняется — это команда alert с вызовом функции pow и передачей ей стартового параметра 5.

alert(pow(5));

Шаг 2

На этом шаге запускается функция pow в строке 3:

Для начинающих программиистов есть интересное общее правило: команды исполняются последовательно, одна за одной по очереди. Здесь же получается, что вызов в 16-й строке, а сама команда запускается из 3-й. Ответ: на самом деле в 3-й строке функция как набор команд просто объявлена и описана, но здесь она ещё не запускается. А вот команда на запуск указана именно в 16-й строке. И второй момент — функция pow при запуске принимает значение 5 из вызова.

Шаг 3

Пока всё просто, значение проверяется на условие: если оно равно 1, то возвращается значение 1 в команду alert. Если значение не равно 1, т.е. результат проверки false, тогда осуществляется переход в else для выполнения размещенных там команд.

Шаг 4

Здесь начинается самое интересное. А именно — здесь есть команда:

return x + pow(x-1);

С одной стороны вроде понятно, что функция pow вызывается заново. Но что при этом происходит с программой в целом?

А происходит то, что эта команда не завершается! Она должна была вернуть (return) в исходный вызов alert какое-то значение. Но проблема в том, что у неё нет этого значения или есть только часть этого значения. На первой итерации, как уже было сказано выше, это значение равно 5. Но к пятерке должна быть добавлена ещё какая-то цифра. И чтобы вычислить эту вторую цифру функция pow запущена заново. Функция запущена заново, а предыдущая команда осталась незавершённой. Это очень важный момент, который я вначале проскочил и скорее всего могут проскочить и другие начинающие программисты.

Вопрос: если команда не завершена, то что с ней происходит? Здесь появляется понятие стека. Само слово «стек» (от английского stack — стог, куча, множество) означает некоторый набор данных. В данном случае это набор незавершённых команд, поскольку у нас тут будет не одна команда, а несколько. Все они доходят до этого места и заворачиваются заново до тех пор, пока передаваемое значение не станет равно 1. Тогда, как было сказано ранее, произойдет return значения 1 в alert. 

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

Самая первая по времени команда pow(5-1) будет помещена в самом низу, а самая последняя pow(2-1) окажется сверху. Именно этих вещей про незавершённость команды и про стек не было в первых темах, из-за чего и произошел затор. И тем более приятно, что удалось их проштудировать самому.

Шаг 5

Не менее интересно, что происходит потом, когда значение уменьшается до 1 и происходит передача 1 в alert. Смысл этой команды понятен, но что происходит после неё?

А происходит то, что функция не останавливается, не завершается, как можно было бы подумать и как действительно тогда мне представлялось. После этой команды начинают выполняться команды из стека, незавершённые команды. Они были запущены, они начали выполняться, но не могли закончить своё выполнение, поскольку их прерывал повторный запуск функции. И вот когда этого повторного запуска уже нет, тогда они и заканчивают своё выполнение. Здесь хорошую иллюстрацию подсказал Женя Жилинский с форума GeekBrains — записать исполнение этого кода матрёшкой, где следующий вызов является «вложенной функцией в предыдущую».

5 + pow(x-1) = 5 + ( 4 + pow(x-1) )= 5 +( 4 +( 3 + pow(x-1) ) ) = 5 +( 4 + ( 3 + (2 + pow(x-1) ) ) ) = 5 + (4 +( 3 +( 2 + 1) ) )

Сначала пружина, можно сказать, сжимается, 5 + (х-1), затем 5 + (4+(х-1)) и т.д., пока «х» не станет числом. И тогда получается простая арифметическая формула,

5 + (4 +( 3 +( 2 + 1)))

где четко видны все числа, входящие во множество, и где в результате мы получаем их сумму равную 15

Выводы по примеру 1

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

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

Пример 2. Второе просветление. Запись состояния функции и незаконченность целостной функции, а не отдельной команды

Как уже было сказано ранее, эта программа выводит на экран последовательность чисел от 11 до 1.

Конструкция кода здесь немного похожа на предыдущий пример, но есть и существенные отличия. Вызов функции делается примерно также из строки после описания самой функции. Но сам вызов прямой, без другой функции (в предыдущем примере там была функция alert). Вызов функции как таковой — Print10 с передачей стартового параметра 1. Функция вывода на печать здесь тоже есть, но она представлена уже другой командой — document.write — и помещена уже в тело самой функции. Условие — не проверка на равенство единице, а проверка на то, что параметр функции должен быть меньше 11.

Общий смысл выполнения кода такой: входной параметр проверяется на условие. Если число меньше 11, то функция запускается заново и к входящему параметру добавляется 1. Когда параметр доходит до значения 11, то повторного вызова функции не происходит, а значит выполняется команда вывода на печать. Самое главное — понять, что именно выводится на печать. Засада случилась именно по этому вопросу, поскольку мне представлялось, что если параметр доходит до 11, то происходит вывод на печать этого числа и всё! Ведь дальше после команды вывода на печать уже больше нет никаких команд, значит ничего больше и не должно происходить. Программа закончена?! 

Но оказывается нет! По факту она печатает еще 10 значений в нисходящем порядке. Интуитивно понимаешь, что это связано с предыдущими проверками условия, но почему это попадает на печать? Оказывается, здесь опять есть «стек» и есть незавершенные операции. Но где они, эти незавершенные операции? Если сравнивать этот пример с предыдущим, то в предыдущим довольно чётко видна незавершённая операция, это команда:

return x + pow(x-1);

Необходимо вернуть «х», который равен определённому значению, например, 5 (или 4, или 3 и т.д.), плюс вторую часть уравнения, которую ещё нужно вычислить — для чего и запускается функция заново. Мы не можем посчитать сумму, потому что нет второй части уравнения. Именно поэтому данная операция незавершённая. Но где незавершённая операция во втором примере? Ведь здесь нет операции сложения, есть только команда повторного вызова функции:

Print10(n+1);

Этот вопрос загнал меня в тупик на несколько дней. Мне показалось, что решение связано с синтаксисом кода. Куда относится команда печати — в else или вообще вне условия if? Вспомнилось правило, что условие if может быть неполным, без else. И второй момент — если в теле условия if один оператор, одна команда, то можно фигурные скобки не ставить. Таким образом, структура функции здесь выглядит так, если её расписать полностью:

Условие if в данном случае неполное, в нём нет второй части else, или она пустая. На форуме GeekBrains обратили внимание на то, что за пустой else могут уволить с работы! А поскольку я ещё не работаю программистом, то в данном случае могу себе позволить рискнуть. И далее, команда document.write к результатам проверки условия отношения не имеет. Отсюда важное следствие — команда вывода на печать будет выполняться всегда, независимо от результатов проверки условия if ! 

Всё это немного прояснило ситуацию, но решения не принесло. Всё выглядело так — 10 раз проверялось условие и функция запускалась заново, после чего печаталось значение 11 и на этом программа должна была завершиться. В упор не видно было, где здесь незавершённая команда — все команды отрабатывают, все завершаются. В результате долгого гугления решение нашлось на стороннем ресурсе — на сайте Тараса Диканева. У него есть страница, специально посвящённая теме рекурсии. Но готового ответа там нет, его подсказал сам автор сайта в индивидуальном общении. А именно:

«Каждый раз, когда одна функция вызывает другую, её состояние (локальные переменные, значения параметров) и точка, где такой вызов произошел, отправляются в стек.»

Здесь ещё одна, третья операция — запись состояния функции!

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

А оказывается, что есть ещё одна операция — запись состояние функции. И выполняется она между этими рекурсивными вызовами. Функция запустилась, выполнена проверка условия, если true (значение меньше 11), то должен быть рекурсивный вызов. Но прежде чем он запустится, делается запись состояния функции, а именно — какие использовались переменные, какие у них значения и из какого места произошел рекурсивный вызов. Последнее или «точка вызова» определяет какая команда будет выполняться следующей. Теперь становится понятной последовательность команд.

Так и появляется незавершённая операция. Это не отдельная команда, а функция в целом. Функция запустилась, проверилось условие и здесь идет повторный, рекурсивный вызов, повторный запуск функции. Получается, что функция не завершена, потому что нужно было ещё напечатать! И так 10 раз функция запускается и прерывается, не завершается. И именно эти операции и помещаются в стек.

Дальше — дело техникии. Когда значение достигает 11, условие выдает false и запускается команда на печать. А за этой первой командой из стека достаются все остальные функции и выводят на печать свои значения. Функция состоит в целом из первой части проверки на условие и вывода на печать. Вывод на печать делается при любом раскладе проверки на условие: больше 11 или меньше — всё равно значение n будет выводиться на печать, потому что команда вывода на печать находится вне условия if. Поэтому все эти команды и исполняются после завершения рекурсии. Они должны были исполниться, но им мешал рекурсивный вызов.

Выводы по примеру 2

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

Пример 3. Третье просветление. Хвостовая рекурсия

Когда я в самом начале статьи привёл этот пример, он казался простым:

Действительно, проверка на условие — печать и вызов заново. Но после двух предыдущих примеров я вдруг заметил одну деталь — здесь рекурсионный вызов находится вне тела условия if ! А это значит, что он должен выполняться независимо от результата проверки на условие! Значит он будет выполняться всегда! Это стало очередным потрясением и пришлось снова удариться в учебную рекурсию — гугл, форумы, вопросы. Решение ещё раз подсказал Тарас Диканев. Цитирую:

«Да, теоретически бесконечно. Практически, либо стек переполнится и программа аварийно завершится, либо «умный» компилятор, поняв, что программа фактически ничего не делает, уберёт лишние вызовы.»

Другими словами: программа зависнет или умный компилятор её остановит. И ещё нагуглил, что такая рекурсия называется «хвостовой», так как она размещается в конце функции, в «хвосте». Таких рекурсионных вызовов следует избегать, чтобы не было всяких «глюков». У того же Тараса Диканева на странице нашёл ещё 2 правила:

1. рекурсионный вызов должен быть именно в теле условия if, и
2. рекурсионный вызов осуществляется с изменяемым параметром (должен передавать значение параметра, отличающееся от значения предыдущего вызова).

Всё это позволяет как раз избежать бесконечного вызова рекурсии.

Три случая применения рекурсии

Ещё одно знание, которое приобрёл в ходе учебных поисков. В каких случаях используется рекурсия? Рекурсию можно использовать в трёх случаях:

1. Для вывода последовательности чисел. Например, вывести на печать последовательность чисел из множества от 1 до 100.
2. Для вывода суммы чисел множества. Например, нужно вывести на печать сумму всех чисел от 1 до 30.
3. Для вывода произведения всех чисел того или иного множества. Например, вывести на печать перемноженные между собой числа от 1 до 50. Такая процедура имеет свое название — вычисление факториала.

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

Заключение

Такие вот были у меня злоключения с рекурсией и как их удалось побороть. Понятно, что это ещё не всё, есть ещё много вопросов, связанных с рекурсией. Но как начальный этап, как этап первого знакомства — это уже состоялось. Из своего ученического опыта по данной теме предложил бы преподавателям GeekBrains использовать пример №1 для первого знакомства с рекурсией. Он более понятный и на нём можно показать какие-то первые вещи: ту же незавершённость операций, стек и др.

Спасибо за внимание, желаю всем успехов! 

does this trait [no job done on the way down] warrant that elimination is possible,

No. A simple example: visiting a binary-tree in post order: no work is done on the way down, yet you need a stack (there are ways to encode that stack in the tree by temporarily modifying the tree, but the stack is fundamentally there).

Yet, there are ways to remove non-terminal recursions without using a stack. But those I know are using additional properties, and notably the one that some operations can be carried in another order than the one used for the recursive version. That’s true for your Fibonacci example (where you also are using the fact that some operations are redundant), and your merge sort one. Detecting that this property holds can be difficult (it could change the stability and error characteristic of a floating point algorithm for instance).

At least two of them are systematic enough that it would be possible to get compilers implementing them (I know that the first has been implemented in compilers).

• the introduction of accumulator parameters. Some cases of non-terminal recursion can be turned into a terminal recursion by introducing an additional parameters and using the associativity of the operation still to be done. That’s the case for a recursive factorial or list-length function:

  int len(list l) {
      if (l == NIL)
          return 0;
      else
          return 1 + len(tail(l));
  }
  

  can be replaced with

  int len_aux(list l, int acc) {
      if (l == NIL)
          return acc;
      else
          return len_aux(tail(l), acc+1);
  }
  
  int len(list l) {
      return len_aux(l, 0);
  }
  

  There are algorithms showing how to do automatically.

• the next technique I’ve used (but don’t remember having seen described in the context of an optimization pass for a compiler) is using memoization as an intermediary step (and thus is valid only for pure function). That is you consider that you are caching the result of the function in a table indexed with its parameters and then see that the table can be computed in another order, sometimes reducing the number of values that need to be kept. That method would be applicable to your Fibonacci program.

Being able to remove recursion for your merge example is even more complex: it is not a pure function but one which mutate state. You can think and deduce that it is possible to change the order of operations to made them suitable for a non-recursive implementation without needing a stack, but such a small description can be useful for a human, expanding it to an algorithm to be implemented in a compiler would need some additional work.

does this trait [no job done on the way down] warrant that elimination is possible,

No. A simple example: visiting a binary-tree in post order: no work is done on the way down, yet you need a stack (there are ways to encode that stack in the tree by temporarily modifying the tree, but the stack is fundamentally there).

Yet, there are ways to remove non-terminal recursions without using a stack. But those I know are using additional properties, and notably the one that some operations can be carried in another order than the one used for the recursive version. That’s true for your Fibonacci example (where you also are using the fact that some operations are redundant), and your merge sort one. Detecting that this property holds can be difficult (it could change the stability and error characteristic of a floating point algorithm for instance).

At least two of them are systematic enough that it would be possible to get compilers implementing them (I know that the first has been implemented in compilers).

• the introduction of accumulator parameters. Some cases of non-terminal recursion can be turned into a terminal recursion by introducing an additional parameters and using the associativity of the operation still to be done. That’s the case for a recursive factorial or list-length function:

  int len(list l) {
      if (l == NIL)
          return 0;
      else
          return 1 + len(tail(l));
  }
  

  can be replaced with

  int len_aux(list l, int acc) {
      if (l == NIL)
          return acc;
      else
          return len_aux(tail(l), acc+1);
  }
  
  int len(list l) {
      return len_aux(l, 0);
  }
  

  There are algorithms showing how to do automatically.

• the next technique I’ve used (but don’t remember having seen described in the context of an optimization pass for a compiler) is using memoization as an intermediary step (and thus is valid only for pure function). That is you consider that you are caching the result of the function in a table indexed with its parameters and then see that the table can be computed in another order, sometimes reducing the number of values that need to be kept. That method would be applicable to your Fibonacci program.

Being able to remove recursion for your merge example is even more complex: it is not a pure function but one which mutate state. You can think and deduce that it is possible to change the order of operations to made them suitable for a non-recursive implementation without needing a stack, but such a small description can be useful for a human, expanding it to an algorithm to be implemented in a compiler would need some additional work.

Устранение рекурсии в общем случае

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

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

Ранее
было показано, что алгоритм, который
рисует кривые Гильберта или Серпинского,
должен включать порядка O(N⁴) шагов,
так что исходные рекурсивные версии
достаточно хороши. Они достигают почти
максимальной возможной производительности
при приемлемой глубине рекурсии.

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

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

Поскольку
новый алгоритм выполняет практически
те же шаги, что и компьютер, можно
поинтересоваться, возрастет ли скорость
вычислений. В Visual Basic
это обычно не выполняется. Компьютер
может выполнять задачи, которые требуются
при рекурсии, быстрее, чем вы можете их
имитировать. Тем не менее, оперирование
этими деталями самостоятельно обеспечивает
лучший контроль над выделением памяти
под локальные переменные, и позволяет
избежать глубокого уровня вложенности
рекурсии.

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

Рассмотрим
следующую обобщенную рекурсивную
процедуру:

Sub
Subr(num)

<1
блок кода>

Subr(<параметры>)

<2
блок кода>

End
Sub

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

=====105

Вначале
пометим первые строки в 1 и 2 блоках кода.
Затем эти метки будут использоваться
для определения места, с которого
требуется продолжить выполнение при
возврате из «рекурсии». Эти метки
используются только для того, чтобы
помочь вам понять, что делает алгоритм —
они не являются частью кода Visual
Basic. В этом примере метки
будут выглядеть так:

Sub
Subr(num)

1 <1
блок кода>

Subr(<параметры>)

2 <2
блок кода>

End
Sub

Используем
специальную метку «0» для обозначения
конца «рекурсии». Теперь можно переписать
процедуру без использования рекурсии,
например, так:

Sub
Subr(num)

Dim
pc As Integer ‘ Определяет, где нужно продолжить
рекурсию.

pc
= 1 ‘ Начать сначала.

Do

Select
Case pc

Case
1

<1
блок кода>

If
(достигнуто условие остановки) Then

‘
Пропустить рекурсию и перейти к блоку
2.

pc
= 2

Else

‘
Сохранить переменные, нужные после
рекурсии.

‘
Сохранить pc = 2. Точка, с которой продолжится

‘
выполнение после возврата из «рекурсии».

‘
Установить переменные, нужные для
рекурсии.

‘
Например, num = num — 1.

:

‘
Перейти к блоку 1 для начала рекурсии.

pc
= 1

End
If

Case
2 ‘ Выполнить 2 блок кода

<2
блок кода>

pc
= 0

Case
0

If
(это последняя
рекурсия) Then Exit Do

‘
Иначе восстановить pc и другие переменные,

‘
сохраненные перед рекурсией.

End
Select

Loop

End
Sub

======106

Переменная
pc,
которая соответствует счетчику программы,
сообщает процедуре, какой шаг она должна
выполнить следующим. Например, при
pc = 1,
процедура должна выполнить 1 блок кода.

Когда
процедура достигает условия остановки,
она не выполняет рекурсию. Вместо этого,
она присваивает pc
значение 2, и продолжает выполнение 2
блока кода.

Если
процедура не достигла условия остановки,
она выполняет «рекурсию». Для этого она
сохраняет значения всех локальных
переменных, которые ей понадобятся
позже после завершения «рекурсии». Она
также сохраняет значение pc
для участка кода, который она будет
выполнять после завершения «рекурсии».
В этом примере следующим выполняется
2 блок кода, поэтому она сохраняет 2 в
качестве следующего значения pc.
Самый простой способ сохранения значений
локальных переменных и pc
состоит в использовании стеков, подобных
тем, которые описывались в 3 главе.

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

Private
Sub Factorial(num As Integer, value As
Integer)

Dim
partial As Integer

1 If
num <= 1 Then

value
= 1

Else

Factorial(num
— 1, partial)

2 value
= num * partial

End
If

End
Sub

После
возврата процедуры из рекурсии, требуется
узнать исходное значение переменной
num,
чтобы выполнить операцию умножения
value = num
* partial.
Поскольку процедуре требуется доступ
к значению num
после возврата из рекурсии, она должна
сохранять значение переменных pc
и num
до начала рекурсии.

Следующая
процедура сохраняет эти значения в двух
стеках на основе массивов. При подготовке
к рекурсии, она проталкивает значения
переменных num
и pc
в стеки. После завершения рекурсии, она
выталкивает добавленные последними
значения из стеков. Следующий код
демонстрирует нерекурсивную версию
подпрограммы вычисления факториала.

Private
Sub Factorial(num As Integer, value As Integer)

ReDim
num_stack(1 to 200) As Integer

ReDim
pc_stack(1 to 200) As Integer

Dim
stack_top As Integer ‘ Вершина
стека.

Dim
pc As Integer

pc
= 1

Do

Select
Case pc

Case
1

If
num <= 1 Then ‘ Это условие остановки. value
= 1

pc
= 0 ‘ Конец рекурсии.

Else ‘
Рекурсия.

‘ Сохранить num и следующее значение pc.

stack_top
= stack_top + 1

num_stack(stack_top)
= num

pc_stack(stack_top)
= 2 ‘ Возобновить с
2.

‘ Начать рекурсию.

num
= num — 1

‘ Перенести блок управления в начало.

pc
= 1

End
If

Case
2

‘
value содержит результат последней

‘
рекурсии. Умножить его на num.

value
= value * num

‘
«Возврат» из «рекурсии».

pc
= 0

Case
0

‘
Конец «рекурсии».

‘
Если стеки пусты, исходный вызов

‘
подпрограммы завершен.

If
stack_top <= 0 Then Exit Do

‘
Иначе восстановить локальные переменные
и pc.

num
= num_stack(stack_top)

pc
= pc_stack(stack_top)

stack_top
= stacK_top — 1

End
Select

Loop

End
Sub

Так
же, как и устранение хвостовой рекурсии,
этот метод имитирует поведение
рекурсивного алгоритма. Процедура
заменяет каждый рекурсивный вызов
итерацией цикла While.
Поскольку число шагов остается тем же
самым, полное время выполнения алгоритма
не изменяется.

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

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

Привет, Хабр! Представляю вашему вниманию перевод статьи «Removing a recursion in Python, part 1» автора Эрика Липперта (Eric Lippert).

На протяжении последних 20 лет я восхищался простоте и возможностям Python, хотя на самом деле никогда не работал с ним и не изучал подробно.

В последнее время я присмотрелся к нему поближе — и он оказался действительно приятным языком.

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

• Игрок находится в произвольной клетке на пронумерованном поле;
• Цель вернуться в клетку №1;
• Если игрок находится на чётной клетке, он платит одну монету и проходит половину пути к клетке №1;
• Если игрок находится на нечётной клетке, он может заплатить 5 монет и сразу перейти на первую клетку или заплатить одну монету и сделать один шаг к клетке №1 — на чётную клетку.

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

Задача имеет очевидное рекурсивное решение:

def cost(s):
  if s <= 1:
    return 0
  if s % 2 == 0:
    return 1 + cost(s // 2) 
  return min(1 + cost(s - 1), 5)

Однако эта программа падала, достигая максимальной глубины рекурсии, вероятнее всего из-за того, что автор вопроса экспериментировал с очень большими числами.
Следовательно возникает вопрос: как превратить рекурсивный алгоритм в итерационный на Python?

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

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

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

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

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

Для начала давайте посмотрим как привести программу к такой форме.

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

def add_one(n):
  return n + 1

def get_min(n):
  return min(n + 1, 5)

def cost(s):
  if s <= 1:
    return 0

  if s % 2 == 0:
    argument = s // 2
    result = cost(argument)
    return add_one(result)

  argument = s - 1
  result = cost(argument)
  return get_min(result)

Вторым шагом я хочу вынести вычисление аргумента в отдельную функцию:

# ...
def get_argument(s):
  if s % 2 == 0:
    return s // 2
  return s - 1

def cost(s):
  if s <= 1:
    return 0

  argument = get_argument(s)
  result = cost(argument)

  if s % 2 == 0:
    return add_one(result) 
  return get_min(result)

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

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

#...
def get_after(s):
  if s % 2 == 0:
    return add_one
  return get_min

def cost(s):
  if s <= 1:
    return 0

  argument = get_argument(s)
  after = get_after(s) # after это функция!
  result = cost(argument)
  return after(result) 

Теперь запишем это в более общей и краткой форме:

#...
def is_base_case(s):
  return s <= 1

def base_case_value(s):
  return 0

def cost(s):
  if is_base_case(s):
    return base_case_value(s)

  argument = get_argument(s)
  after = get_after(s)
  return after(cost(argument)) 

Видно, что каждое проделанное изменение сохраняло смысл программы.

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

Если мы захотим, то можем решить эту проблему объединив две вспомогательные функции в одну, возвращающую кортеж.

Но давайте не будем беспокоиться об этом в рамках решения этой задачи.

Мы свели наш рекурсивный метод до максимально общей формы.

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

Кое-что важное на что необходимо обратить внимание на этом шаге — это то, что after не должен сам содержать вызовов cost.

Способ, который я показываю здесь, удаляет единственный рекурсивный вызов.

Если у вас 2 и более рекурсии, то нам понадобится другое решение.

Как только мы привели наш рекурсивный алгоритм к такой форме, преобразовать его в итеративный уже просто.

Хитрость в том, чтобы представить, что происходит в рекурсивной программе.

Как мы делаем рекурсивный спуск: мы вызываем get_argument перед рекурсивным вызовом и вызываем функцию after после возврата из рекурсии.

То есть, все вызовы get_argument происходят перед всеми вызовами after.
Поэтому мы можем преобразовать это в 2 цикла: первый вызывает get_argument и формирует список функций after, а второй вызывает все функции after:

#...
def cost(s):
  # Создаём стек из функций "after". Все эти функции
  # принимают результат рекурсивного вызова и возвращают
  # значение, которое вычисляет рекурсивный метод.
  afters = [ ]
  while not is_base_case(s):
    argument = get_argument(s)
    after = get_after(s)
    afters.append(after)
    s = argument
  # Теперь у нас есть стек функций "after" :
  result = base_case_value(s)
  while len(afters) != 0:
    after = afters.pop()
    result = after(result)
  return result

Больше никакой рекурсии!

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

Этот пример отражает мысль, которую я часто повторяю о стеке вызовов: его цель сообщить то, что произойдёт дальше, а не то, что уже произошло!

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

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

В следующий раз мы рассмотрим более сложный способ удаления рекурсии на Python.

You might have seen a Python recursion error when running your Python code. Why does this happen? Is there a way to fix this error?

A Python RecursionError exception is raised when the execution of your program exceeds the recursion limit of the Python interpreter. Two ways to address this exception are increasing the Python recursion limit or refactoring your code using iteration instead of recursion.

Let’s go through some examples so you can understand how this works.

The recursion begins!

Let’s create a program to calculate the factorial of a number following the formula below:

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

Write a function called factorial and then use print statements to print the value of the factorial for a few numbers.

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

This is a recursive function…

A recursive function is a function that calls itself. Recursion is not specific to Python, it’s a concept common to most programming languages.

You can see that in the else statement of the if else we call the factorial function passing n-1 as parameter.

The execution of the function continues until n is equal to 0.

Let’s see what happens when we calculate the factorial for two small numbers:

if __name__ == '__main__': 
    print("The factorial of 4 is: {}".format(factorial(4)))
    print("The factorial of 5 is: {}".format(factorial(5)))

[output]
The factorial of 4 is: 24
The factorial of 5 is: 120 

After checking that __name__ is equal to ‘__main__’ we print the factorial for two numbers.

It’s all good.

But, here is what happens if we calculate the factorial of 1000…

print("The factorial of 1000 is: {}".format(factorial(1000)))

[output]
Traceback (most recent call last):
  File "recursion_error.py", line 9, in <module>
    print("The factorial of 1000 is: {}".format(factorial(1000)))
  File "recursion_error.py", line 5, in factorial
    return n*factorial(n-1)
  File "recursion_error.py", line 5, in factorial
    return n*factorial(n-1)
  File "recursion_error.py", line 5, in factorial
    return n*factorial(n-1)
  [Previous line repeated 995 more times]
  File "recursion_error.py", line 2, in factorial
    if n <= 1:
RecursionError: maximum recursion depth exceeded in comparison 

The RecursionError occurs because the Python interpreter has exceeded the recursion limit allowed.

The reason why the Python interpreter limits the number of times recursion can be performed is to avoid infinite recursion and hence avoid a stack overflow.

Let’s have a look at how to find out what the recursion limit is in Python and how to update it.

What is the Recursion Limit in Python?

Open the Python shell and use the following code to see the value of the recursion limit for the Python interpreter:

>>> import sys
>>> print(sys.getrecursionlimit())
1000 

Interesting…the limit is 1000.

To increase the recursion limit to 1500 we can add the following lines at the beginning of our program:

import sys
sys.setrecursionlimit(1500)

If you do that and try to calculate again the factorial of 1000 you get a long number back (no more errors).

The factorial of 1000 is: 4023872600770937735437024339230039857193748642107146325437999104299385123986290205920
.......835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

That’s good! But…

…this solution could work if like in this case we are very near to the recursion limit and we are pretty confident that our program won’t end up using too much memory on our system.

How to Catch a Python Recursion Error

One possible option to handle the RecursionError exception is by using try except.

It allows to provide a clean message when your application is executed instead of showing an unclear and verbose exception.

Modify the “main” of your program as follows:

if __name__ == '__main__':
    try:
        print("The factorial of 1000 is: {}".format(factorial(1000)))
    except RecursionError as re:
        print("Unable to calculate factorial. Number is too big.") 

Note: before executing the program remember to comment the line we have added in the section before that increases the recursion limit for the Python interpreter.

Now, execute the code…

You will get the following when calculating the factorial for 1000.

$ python recursion_error.py
Unable to calculate factorial. Number is too big. 

Definitely a lot cleaner than the long exception traceback.

Interestingly, if we run our program with Python 2.7 the output is different:

$ python2 recursion_error.py 
Traceback (most recent call last):
  File "recursion_error.py", line 13, in <module>
    except RecursionError as re:
NameError: name 'RecursionError' is not defined 

We get back a NameError exception because the exception of type RecursionError is not defined.

Looking at the Python documentation I can see that the error is caused by the fact that the RecursionError exception was only introduced in Python 3.5:

So, if you are using a version of Python older than 3.5 replace the RecursionError with a RuntimeError.

if __name__ == '__main__':
    try:
        print("The factorial of 1000 is: {}".format(factorial(1000)))
    except RuntimeError as re:
        print("Unable to calculate factorial. Number is too big.") 

In this way our Python application works fine with Python2:

$ python2 recursion_error.py
Unable to calculate factorial. Number is too big. 

How Do You Stop Infinite Recursion in Python?

As we have seen so far, the use of recursion in Python can lead to a recursion error.

How can you prevent infinite recursion from happening? Is that even something we have to worry about in Python?

Firstly, do you think the code we have written to calculate the factorial could cause an infinite recursion?

Let’s look at the function again…

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

This function cannot cause infinite recursion because the if branch doesn’t make a recursive call. This means that the execution of our function eventually stops.

We will create a very simple recursive function that doesn’t have an branch breaking the recursion…

def recursive_func():
    recursive_func()

recursive_func() 

When you run this program you get back “RecursionError: maximum recursion depth exceeded”.

$ python recursion_error2.py
Traceback (most recent call last):
  File "recursion_error2.py", line 4, in <module>
    recursive_func()
  File "recursion_error2.py", line 2, in recursive_func
    recursive_func()
  File "recursion_error2.py", line 2, in recursive_func
    recursive_func()
  File "recursion_error2.py", line 2, in recursive_func
    recursive_func()
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

So, in theory this program could have caused infinite recursion, in practice this didn’t happen because the recursion depth limit set by the Python interpreter prevents infinite recursion from occurring.

How to Convert a Python Recursion to an Iterative Approach

Using recursion is not the only option possible. An alternative to solve the RecursionError is to use a Python while loop.

We are basically going from recursion to iteration.

def factorial(n):
    factorial = 1

    while n > 0:
        factorial = factorial*n
        n = n - 1

    return factorial

Firstly we set the value of the factorial to 1 and then at each iteration of the while loop we:

• Multiply the latest value of the factorial by n
• Decrease n by 1

The execution of the while loop continues as long as n is greater than 0.

I want to make sure that this implementation of the factorial returns the same results as the implementation that uses recursion.

So, let’s define a Python list that contains a few numbers. Then we will calculate the factorial of each number using both functions and compare the results.

We use a Python for loop to go through each number in the list.

Our program ends as soon as the factorials calculated by the two functions for a given number don’t match.

def factorial(n):
    factorial = 1

    while n > 0:
        factorial = factorial*n
        n = n - 1

    return factorial

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

numbers = [4, 9, 18, 23, 34, 56, 78, 88, 91, 1000] 

for number in numbers:
    if factorial(number) != recursive_factorial(number):
        print("ERROR: The factorials calculated by the two functions for the number {} do not match.".format(number))

print("SUCCESS: The factorials calculated by the two functions match") 

Let’s run our program and see what we get:

$ python factorial.py
SUCCESS: The factorials calculated by the two functions match 

Great!

Our implementation of the factorial using an iterative approach works well.

Conclusion

In this tutorial we have seen why the RecursionError occurs in Python and how you can fix it.

Two options you have are:

• Increase the value of the recursion limit for the Python interpreter.
• Use iteration instead of recursion.

Which one are you going to use?

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

Устранение непосредственной левой рекурсии

Опишем процедуру, устраняющую все правила вида , для фиксированного нетерминала .

1. Запишем все правила вывода из в виде:
   , где
   • — непустая последовательность терминалов и нетерминалов ();
   • — непустая последовательность терминалов и нетерминалов, не начинающаяся с .
2. Заменим правила вывода из на .
3. Создадим новый нетерминал .

Изначально нетерминал порождает строки вида . В новой грамматике нетерминал порождает , а порождает строки вида . Из этого очевидно, что изначальная грамматика эквивалентна новой.

Пример

Есть непосредственная левая рекурсия . Добавим нетерминал и добавим правила , .

Новая грамматика:

В новой грамматике нет непосредственной левой рекурсии, но нетерминал леворекурсивен, так как есть

Алгоритм устранения произвольной левой рекурсии

Воспользуемся алгоритмом удаления -правил. Получим грамматику без -правил для языка .

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

Пусть — упорядоченное множество всех нетерминалов.

 for 
   for 
     for 
       удалить продукцию  
       for 
         добавить правило 
   устранить непосредственную левую рекурсию для 

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

После итерации внешнего цикла в любой продукции внешнего цикла в любой продукции вида , должно быть . В результате при следующей итерации внутреннего цикла растет нижний предел всех продукций вида до тех пор, пока не будет достигнуто .

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

На итерации внешнего цикла все правила вида где заменяются на где . Очевидно, что одна итерация алгоритма не меняет язык, а значит язык получившийся в итоге грамматики совпадает с исходным.

Оценка времени работы

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

Худший случай

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

Пример грамматики для которой имеет значение порядок нетерминалов

для

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

Порядок выбора нетерминалов

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

Это действие удаляет левую рекурсию только если — леворекурсивный нетерминал и содержится в выводе (то есть — левый вывод из ,в то время как — левый вывод из ).

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

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

Пример

Дана грамматика:

Среди правил непосредственной рекурсии нет, поэтому во время первой итерации внешнего цикла ничего не происходит.
Во время второй итерации внешнего цикла правило переходит в .

Грамматика имеет вид

Устраняем левую рекурсию для

См. также

• Контекстно-свободные грамматики
• Нормальная форма Хомского
• Удаления -правил из грамматики

Источники информации

• Хопкрофт Д., Мотвани Р., Ульман Д. — Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)
• Robert C. Moore — Removing Left Recursion from Context-Free Grammars