Unravel recursion inside double for loop to avoid stack overflow

Question

I have the following code. It's about as simple as I can make it. Does anyone know of a slick way to turn this recursion into a loop?

The problem is that I can run into a recusion limit. I've thought of some ways to rewrite it, but they're not pretty at all.

My nicest thought at this point is that I could get it into some tail recursion form, but I'm not sure how to do that.

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)]

Example: recurse(6, 1000) throws an error is way over the recursion limit.

Cool, mostly useless fact: Using range(i, c + 1) for the black box returns all the lists with length length with sum at most c.

EDIT: I'm aware I can memoize the code, but that doesn't fix recursion limit. In this example, memoizing helps the speed a lot, but in my situation it doesn't, so I'm not concerned with it.

EDIT 2: Updated blackbox so the value of recurse(6,1000) is reasonable.

Michael Butscher · Accepted Answer · 2020-04-08 01:09:40Z

1

One way can be to use your own stack of generator functions instead:

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))

Slightly shorter variant but needs more care:

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))

While in the first variant nonrecurse was a generator function, it is now a usual function returning generators where the list comprehension is a generator on its own.

edited Apr 8, 2020 at 1:09

answered Apr 8, 2020 at 0:47

Michael Butscher

11k4 gold badges28 silver badges28 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Jay Over a year ago

I'm going to have to read up on python's generator function concept before I can accurately judge this. I noticed that it appears to only work for python 3. I would like my code to run on both python 2 and 3. Is this the type of thing that only works in python 3? Edit: the error is SyntaxError: 'return' with argument inside generator. But, it runs perfect with python3.

Jay Over a year ago

Ok, I got it to work and simplified it a good bit. I'll edit your answer with my changes and mark is as the answer.

Collectives™ on Stack Overflow

Unravel recursion inside double for loop to avoid stack overflow

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related