Устранение рекурсии в Python

Привет, Хабр! Представляю вашему вниманию перевод статьи "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.