Распутайте рекурсию внутри double для l oop, чтобы избежать переполнения стека - PullRequest
Новая
       7

Распутайте рекурсию внутри double для l oop, чтобы избежать переполнения стека

0 голосов
/ 08 апреля 2020

У меня есть следующий код. Это так просто, как я могу это сделать. Кто-нибудь знает хитрый способ превратить эту рекурсию в al oop?

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

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

def blackbox(c, i): #This is a different function in production
    if i > 5:
        return range(0,1)
    else:
        return range(0,c+i)

def recurse(c, length):
    if length == 0:
        return [[]]
    return [l + [j] for j in blackbox(c, length) for l in recurse(c - j, length - 1)]

Пример: recurse(6, 1000) выдает ошибку, превышающую предел рекурсии.

Классный, в основном бесполезный факт: использование range(i, c + 1) для черный ящик возвращает все списки длиной length с суммой не более c.

РЕДАКТИРОВАТЬ: я знаю, что могу запомнить код, но это не фиксирует ограничение рекурсии. В этом примере запоминание очень помогает скорости, но в моей ситуации это не так, поэтому меня это не касается.

РЕДАКТИРОВАТЬ 2: Обновлено blackbox, поэтому значение recurse(6,1000) равно разумно.

1 Ответ

1 голос
/ 08 апреля 2020

Вместо этого можно использовать собственный стек функций генератора: 

def blackbox(c, i):
    return range(0, c + i) #This code is actually quite different, treat it as a black box

# For testing at the end
def recurse(c, length):
    if length == 0:
        return [[]]
    return [l + [j] for j in blackbox(c, length) for l in recurse(c - j, length - 1)]



# Non-recursive variant following:

gen_stack = []

def gen_driver():
    prevResult = None

    while gen_stack:
        try:
            if prevResult is not None:
                gen_stack[-1].send(prevResult)
                prevResult = None
            else:
                next(gen_stack[-1])
        except StopIteration as si:
            prevResult = si.value
            del gen_stack[-1]

    return prevResult


def nonrecurse(c, length):
    if length == 0:
        return [[]]

    # Unfortunately the concise list comprehension doesn't work
    result = []
    for j in blackbox(c, length):
        gen_stack.append(nonrecurse(c - j, length - 1))
        for l in (yield):
            result.append(l + [j])

    return result


gen_stack.append(nonrecurse(6, 10))

# Testing equality of both variants
print(gen_driver() == recurse(6,10))

# No crash but I didn't wait until it was ready
gen_stack.append(nonrecurse(6, 1000))

Немного более короткий вариант, но требует большей осторожности: 

gen_stack = []

def gen_driver():
    prevResult = None

    while gen_stack:
        try:
            if prevResult is not None:
                gen_stack.append(gen_stack[-1].send(prevResult))
                prevResult = None
            else:
                gen_stack.append(next(gen_stack[-1]))
        except StopIteration as si:
            prevResult = si.value
            del gen_stack[-1]

    return prevResult


def single_generator(value):
    return value
    yield # Mark it as generator function


def nonrecurse(c, length):
    if length == 0:
        return single_generator([[]])

    return [l + [j] for j in blackbox(c, length) for l in (yield nonrecurse(c - j, length - 1))]


gen_stack.append(nonrecurse(6, 10))

# Testing equality of both variants
print(gen_driver() == recurse(6,10))

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

...