python - 如何退出非尾递归而不计算额外结果？

Question

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

 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 ，而在其他情况下它返回非 None 内容。

因此，当您进行递归调用时，只需检查返回值即可，如果是这种情况，则返回而不继续多余的计算。也就是说，而不是

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