Nadin_Leo Feb 13 2019 at 15:24

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

4 min

20K

Python*Programming*Algorithms*

From sandbox

+24

Comments 12

PYXRU Feb 13 2019 at 16:43

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

Я то к тому, то что вы написали не панацея, и не всегда может быть применена, лучше озаглавить «оптимизация рекурсивного алгоритма для задачи # .....»

Mingun Feb 13 2019 at 18:35

Почему же не всегда? По-моему, очень общее решение. Главное помнить, что в функцию можно передавать не один аргумент, а вектор аргументов, из результатов всех предыдущих рекурсивных вызовов (или заглушек для последних N вызовов, где N — количество рекурсивных вызовов), а возвращать — те же аргументы, смещенные на одну позицию + новое значение. И тогда любую рекурсию можно развернуть. Во всяком случае мне не удается придумать контрпример.

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

PYXRU Feb 13 2019 at 18:40

Я про то что хранить результаты последних вызовов, это не всегда надо, можно допустим только четных или нечетных, задачу можно любую придумать. А хвостовую рекурсию всегда можно развернуть достаточно просто, как минимум в массив линейных результатов. stackoverflow.com/questions/931762/can-every-recursion-be-converted-into-iteration/933979#933979

Rambalac Feb 13 2019 at 18:51

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

Mingun Feb 13 2019 at 22:44

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

UFO just landed and posted this here

longclaps Feb 14 2019 at 09:33

def cost(s, cache=[0, 0]):
    if s >= len(cache):
        for i in range(len(cache), s + 2, 2):
            c = cache[i // 2] + 1
            cache += c, min(c + 1, 5)
    return cache[s]

Лучше бы Eric Lippert восхищался питоном молча.

mayorovp Feb 14 2019 at 10:03

А зачем тут if?

longclaps Feb 14 2019 at 10:17

Это — ленивый алгоритм с кэшем, он проверяет, нет ли уже значения для s в кэше.

mayorovp Feb 14 2019 at 10:23

Я понимаю что это за алгоритм. Но зачем в нём первая строчка? Он и без неё должен работать.

longclaps Feb 14 2019 at 10:28

Можно и без неё, но при попадании в кэш будет немного медленнее.

python273 Feb 15 2019 at 12:11

Как-то сделал модуль, с которым можно рекурсивные вызовы поменять на yield и поменять return на raise StopIteration(...), а он бы под капотом остановленные генераторы в стек складывал.

def sumrange(x):
    if x == 0:
        return 0

    r = sumrange(x - 1)
    return x + r

print(sumrange(10))  # 55
print(sumrange(1000))
# RecursionError: maximum recursion depth exceeded

from precursion import precurse

@precurse
def sumrange(x):
    if x == 0:
        raise StopIteration(0)

    r = yield sumrange.r(x - 1)
    raise StopIteration(x + r)

print(sumrange(1000))  # 500500!!1

https://github.com/python273/precursion (правда сломано в 3.7)
https://github.com/python273/precursion/blob/master/precursion/precursion.py#L28-L51

Show the best of all time