如何在不计算额外结果的情况下退出非尾递归？

Question

我有一个非尾递归 ( )。我有两个 "correct" 答案，其中一个我认为不是正确答案，但我也在我公认的大量调试打印语句中注意到，尽管找到了答案，但程序在退出递归时仍在计算.有没有办法中断这个或者这两个部分是同一个问题？

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

对于那些感兴趣的人，这是实施 Steven Skiena 对限制性片段映射的部分摘要问题的解决方案的尝试。 Antonio Perez has a generally better, conceptually similar solution 超过 GitHub，但他的实现似乎有同样的问题。

Answer 1

你的代码中可能是递归终止的部分

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

正在做 pretty much the same as returning None，而在其他情况下 return 是非 None 的东西。

因此，当您进行递归调用时，只需为此检查 return 值，如果是这种情况，则 return 无需继续进行冗余计算。也就是说，而不是

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

使用

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

这里有一些糟糕的软件工程，但足够好的生物信息学。 Ami 的答案更糟糕，但您可能更容易实施。

您可以 raise 异常来表示计算已完成。一开始，在你的函数之前，你写：

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

所以一旦你知道你有答案，你就去

if Answer found:
    #  print it
    raise Done

然后当你调用整个函数时，它会在找到第一个答案后立即停止所有级别的递归。它也会退出你的整个程序，除非你用 try 块调用函数，

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

再一次，这是糟糕的软件工程：纯粹主义者可能会生你的气！然而，在更复杂的递归中很容易得到正确的结果，而不必正确地探测所有的退出情况。

如何在不计算额外结果的情况下退出非尾递归？

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

python

algorithm

recursion

bioinformatics