Устранение рекурсии в Python
Привет, Хабр! Представляю вашему вниманию перевод статьи «Removing a recursion in Python, part 1» автора Эрика Липперта (Eric Lippert).
На протяжении последних 20 лет я восхищался простоте и возможностям Python, хотя на самом деле никогда не работал с ним и не изучал подробно.
В последнее время я присмотрелся к нему поближе — и он оказался действительно приятным языком.
Недавний вопрос на StackOverflow заставил меня задуматься, как преобразовать рекурсивный алгоритм в итеративный, и оказалось, что Python довольно подходящий язык для этого.
Проблема с которой столкнулся автор вопроса заключалась в следующем:
- Игрок находится в произвольной клетке на пронумерованном поле;
- Цель вернуться в клетку №1;
- Если игрок находится на чётной клетке, он платит одну монету и проходит половину пути к клетке №1;
- Если игрок находится на нечётной клетке, он может заплатить 5 монет и сразу перейти на первую клетку или заплатить одну монету и сделать один шаг к клетке №1 — на чётную клетку.
Вопрос заключается в следующем: какое наименьшее количество монет необходимо заплатить, чтобы вернуться из текущей клетки в первую.
Задача имеет очевидное рекурсивное решение:
Однако эта программа падала, достигая максимальной глубины рекурсии, вероятнее всего из-за того, что автор вопроса экспериментировал с очень большими числами.
Следовательно возникает вопрос: как превратить рекурсивный алгоритм в итерационный на 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 Вторым шагом я хочу вынести вычисление аргумента в отдельную функцию:
# . def get_argument(s): if s % 2 == 0: return s // 2 return s - 1 def cost(s): if s На третьем шаге, я хочу добавить вспомогательную функцию, которая будет выбирать функцию-продолжение, вызываемую после возврата из рекурсии.
Обратите внимание, что вспомогательная функция возвращает функцию.
#. def get_after(s): if s % 2 == 0: return add_one return get_min def cost(s): if s Теперь запишем это в более общей и краткой форме:
#. def is_base_case(s): return s Видно, что каждое проделанное изменение сохраняло смысл программы.
Сейчас проверка на чётность числа выполняется дважды, хотя до изменений проверка была одна.
Если мы захотим, то можем решить эту проблему объединив две вспомогательные функции в одну, возвращающую кортеж.
Но давайте не будем беспокоиться об этом в рамках решения этой задачи.
Мы свели наш рекурсивный метод до максимально общей формы.
- В базовом случае:
- вычисляем значение, которое нужно вернуть;
- возвращаем его.
- вычисляем аргумент рекурсии;
- производим рекурсивный вызов;
- вычисляем возвращаемое значение;
- возвращаем его.
Кое-что важное на что необходимо обратить внимание на этом шаге — это то, что 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.
Как досрочно остановить рекурсию
У меня есть код, который из значения 100 рекурсивно уменьшается до 0 вычитая 20 . Вопрос, можно ли досрочно остановить, или поставить точку остановки и вывести например первую итерацию, чтобы я мог далее обращаться к данному значению?
чтобы например при вызове req(100) я мог получить значение 100, затем 80, но отдельно а не полным циклом например записать в переменную temp = req(100) значение 100
мне нужно чтобы я мог обращаться к каждому значению до самого 0, то есть, чтобы каждый раз вызывал функцию, у меня там было значение 80, потом вызов и 60 и тд. Все это можно сделать через while, но интересно узнать можно ли сделать это через рекурсию
3 ответа 3
Используя генератор можно сделать так
def req(value): yield value if value100 Данное значение: 100 80 Данное значение: 80 60 Данное значение: 60Прощу прощения, немного не так поставил вопрос, мне нужно чтобы после каждой итерации рекурсии она выходила из цикла, то есть: Я вызываю функцию req, она возвращает 80 и останавливается, затем я вновь вызываю функцию и получаю уже 60
def req(value): return value-20 Те в функции просто выполняйте одну итерацию. Используя partial можно настроить один раз параметры итерации
Можно попытаться ввести счетчик итераций, если я вас правильно понял.
def req(value, count): if valueiterator = iter(range(100, -1, -20)) def get_next(): try: return next(iterator) except StopIteration: return 0 print(get_next()) print(get_next()) print(get_next()) print(get_next()) print(get_next()) print(get_next()) print(get_next()) print(get_next())или вариант с зацикленным итератором:
default_range = range(100, -1, -20) iterator = iter(default_range) def get_next(): global iterator try: return next(iterator) except StopIteration: iterator = iter(default_range) return next(iterator) print(get_next()) print(get_next()) print(get_next()) print(get_next()) print(get_next()) print(get_next()) print(get_next()) print(get_next())default_range = range(100, -1, -20) iterator = iter(default_range) def get_next(): global iterator try: return next(iterator) except StopIteration: iterator = iter(default_range) return next(iterator) print( f'First value = , Second value = ' )First value = 100, Second value = 80How to stop python recursion
I made a function that searches files recursively and I want it to stop recursion when the first file is found:
def search_file(path): for name in os.listdir(path): sub = os.path.join(path, name) if os.path.isfile(sub): return sub#And break recursion else: search_file(sub)4 Answers 4
Return a flag that says whether the file was found. When you call search_file , return if the return value is True.
You are close. You already break recursion when you find the file, the problem is that you didn't propegate that result all the way up the chain. A well-placed print statement would show what went wrong.
import os def search_file(path): for name in os.listdir(path): sub = os.path.join(path, name) print('peek at: <>'.format(sub)) if os.path.isfile(sub): return sub#And break recursion else: sub = search_file(sub) if sub: return sub print(search_file('a'))@NeilG If the failure return is outside the for loop for readability initialize the sub value to None or explicitly return None.
Note that you need to be able to return a false entry in case it loops all the way down without finding anything. However, you do not want to break out of the for loop if nothing found in one subdirectory without checking the next sub directory. The return will break out of the function, returning the results without having to enter a break.
def search_file(path): Initialize results to no file found val = False sub = None for name in os.listdir(path): sub = os.path.join(path, name) val = os.path.isfile(sub): if val: return val, sub #And break recursion else: #check the subdirectory. val, sub = search_file(sub) # Break out if a valid file was found. if val: return val, sub # No files found for this directory, return a failure return val, subOn the other hand, if you want to have only one return, you can use a break as follows
def search_file(path): Initialize results to No file found val = False sub = None for name in os.listdir(path): sub = os.path.join(path, name) val = os.path.isfile(sub): if val: break # break out of the for loop and return else: #check the subdirectory. val, sub = search_file(sub) # Break out if a valid file was found. if val: break # Return the True or False results return val, sub