How to exit a non-tail recursion without computing additional results?

Question

I have a non-tail recursion in place( ). I have two "correct" answers, one of which I don't think is a correct answer, but I also noticed in my admittedly copious debugging print statements that the program keeps calculating as it exits the recursion, despite having found the answer. Is there a way to interrupt this or are these two parts of the same problem?

 def partialDigest(l):
    width = max(l)
    l.remove(width)
    x = [0, width]
    place(l, x, width, level=0)

def place(l, x, width, level):
    level = level + 1
    print('level',level)
    if not l:
        print('done!', x)
        return
    y = max(l)
    print('y',y)
    print('a', [abs(i-y) for i in x], l)
    if subset([abs(i-y) for i in x], l):
        print('choose a')
        print('x',sorted(x))
        print('l',sorted(l))
        print('append y to x and remove delta(x) from l')
        remove_lengths([abs(i-y) for i in x], l)
        x.append(y)
        print('x',sorted(x))
        print('l',sorted(l))
        print ('run place')
        place(l, x, width, level)
        print('remove y from x and add lengths to l')
        add_lengths([abs(i-y) for i in x], l)
        x.remove(y)
    print('b', [abs(i-(width-y)) for i in x], l)
    if subset([abs(i-(width-y)) for i in x], l):
        print('choose b')
        print('x',sorted(x))
        print('l',sorted(l))
        print('append (width - y) to x and remove lengths from l')
        remove_lengths([abs(i-(width - y)) for i in x], l)
        x.append(width - y)
        print('x',sorted(x))
        print('l',sorted(l))
        print('run place')
        place(l, x, width, level)
        print('remove (width - y) from x and add lengths to l')
        add_lengths([abs(i-(width-y)) for i in x], l)
        x.remove(width - y)
    else:
        print('c')
    print x, l
    print('return to level', level)
    return x, l

def remove_lengths(x, l):
    for i in x:
        if i in l:
            l.remove(i)
    return l

def add_lengths(x, l):
    for i in x:
        if i != 0:
            l.append(i)
    return l

def subset(list1, list2):
    x = True
    for i in list1:
        if i not in list2:
            x = False
    return x

l = [2, 2, 3, 3, 4, 5, 6, 7, 8, 10]
print(partialDigest(l))

For those interested, this is an attempt to implement Steven Skiena's solution to the partial digest problem for restriction fragment mapping. Antonio Perez has a generally better, conceptually similar solution over on GitHub, but his implementation seems like it would have the same issue.

Answer 1

The part of your code which is presumably the recursion termination

if not l:
    print('done!', x)
    return

is doing pretty much the same as returning None, whereas it returns non-None stuff in other cases.

So, when you do the recursive calls, just check the return value for this, and return without continuing the redundant calculations if this is the case. That is, instead of

foo(...) # I'm calling foo
# and continuing unconditionally,

use

if foo(...) is None: # If someone below me reached the termination
    return # Then I will propagate the termination having been reached, and won't continue

Answer 2

Here's some bad software engineering, but good-enough bio-informatics. It's worse that Ami's answer, but might be easier for you to implement.

You could raise an Exception to signal that computation is completed. At the start, before your function, you write:

class Done(Exception):
    """Completed recursion and found answer."""
    # No body required

So as soon as you know you have the answer, you go

if Answer found:
    #  print it
    raise Done

Then when you call the whole function, it will stop all of the levels of recursion as soon as the first answer is found. It will ALSO quit your whole program, unless you call the function with a try block,

try:
    place(l, x, width, level=0)
except Done:
    # We expected this, nothing to do
    pass

Once again, this is bad software engineering: purists might get angry with you! However, it's easy get right in more complicated recursions without having to plumb all the exit cases correctly.