python - 如何跟踪这个递归程序

Question

我想知道是否有人能告诉我这个程序是如何得出正确答案的。我试图追踪它，但不确定去哪里，因为它有一个 或 ，所以我很困惑，应该如何追踪它。感谢您的澄清。

编写一个函数分区，它采用数字列表 xs、起始位置 i 和所需的总和 s 并返回 True 或 False 取决于是否可以找到从位置 i 开始的列表元素的子序列，其总和正好是 s。请注意，总有可能产生一个元素的和正好为 0 的子序列，即元素的空序列。

def partition(xs,i,s):
    print i,s
    if i == len(xs):
        return s == 0
    else:
        return partition(xs,i+1,s-xs[i]) or partition(xs,i+1,s)

Answer 1

rcviz模块是帮助可视化递归函数的好工具:

The edges are numbered by the order in which they were traversed by the execution. 2. The edges are colored from black to grey to indicate order of traversal : black edges first, grey edges last.

如果您跟踪编号为 1-11 的调用，您可以准确地看到发生了什么，i 从 0 开始，然后转到1、2、3 最后是 4，左边的最后一个值是 partitition([1,2,3,4],4,-2) 所以它为 s == 返回 False 0。

接下来我们回到 i 是 2 的地方，然后又是 3,4 并以 partitition([1,2,3,4], 4,1) 所以 s == 1 又是 False。

接下来我们从步骤 6 开始，以 partitition([1,2,3,4],4,5) 结束，这里 s == 0 为假。

最后在右边，我们从 partitition([1,2,3,4],4,7) 一直到 partitition([1,2,3, 4],4,0) 其中 s == 0 为 True，函数返回 True。

如果你接前四个调用，你可以看到流程是如何进行的，s 是如何变化的。

 partitition([1,2,3,4],1,7)  # -> xs[i] = 1 s - 1 = 7
 partitition([1,2,3,4],2,5)  # -> xs[i] = 2 s - 2 = 5
 partitition([1,2,3,4],2,5)  # -> xs[i] = 3 s - 3 = 2
 partitition([1,2,3,4],2,5)  # -> xs[i] = 4 s - 4 = -2
 s == 0 # -> False