python - 如何手动确定复杂递归函数的输出

Question

这是有问题的递归代码:

def trace(a, b):
    if (a > b):
        return -1
    elif (a == b):
        print (a * a)
        return a * a
    else:
        m = (a + b) / 2
        return trace (a, m) + trace (m + 1, b)

x=trace(1,4)

虽然我不确定这个函数应该做什么，但我们应该手动找到 x=trace(1,4) 的输出以及 x 的值(这意味着我们不能使用空闲来帮助我们)。

过了一段时间，我确定该函数将打印 1 和 12.25，这将是将 x 分配给 trace(1,4) 时的输出。

但是，我不知道如何确定 X 的值。虽然答案是-91.75，但我完全不知道它是如何得出的(虽然我知道如何得出这个答案，但需要很长时间才能得出这个答案，而且我不确定我们如何才能快速得出在短时间内解决，例如在考试时)。

预先感谢您的帮助!

Answer 1

首先，我作弊了。我的胸口有一些提示:该函数绝对不是为 Python 3 设计的!原因是/运算符。在Python 2 中它产生整数，在Python3 中它产生 float 。因此，记住这个前提条件就是我的解决方案:

功能并不复杂。每个变量的数据类型都是整数! m 始终是整数。 x 为 30。递归级别为三，相当于对函数的七次调用(包括第一次)。以下是处理此类事情的方法:拿一些纸和笔，写下每一个步骤。

1. 输入是:a=1 和 b=4，这导致函数中的 else 部分...到目前为止没有输出。其中m计算为(1+4)/2。在我的书中，这个数字是 2.5。但这会四舍五入为 2，因为我们有整数。然后递归从两次调用 (1,2) 和 (3,4) 开始
2. 让我们看看 (1,2):a=1 和 b=2。再次，没有输出，我们直接进入 else 部分:m 计算为 3/2，这是一个很好的 1.5 四舍五入到 1。再次使用新参数 (1,1) 和 (2, 2) 两次调用该函数。请注意，两个调用现在都将进入函数的 elif 部分，并且每个调用都会产生一个输出和一个返回值。可以将(1,1)替换为1，(2,2)替换为4。这里完成了递归，调用trace(1,2)得到5。让我们看看递归的另一个分支。
3. 输入是 a=3 和 b=4，这会导致另一对具有以下参数的调用:(3,3) 和 (4,4)。我想现在你应该掌握窍门了。有趣的部分是按照提供的方式将所有返回值相加。

至于该函数的作用:它对 a 和 b 之间的所有整数的所有平方求和。