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

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的值的输出(意思是我们不能使用idle来帮助我们).

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

但是,我不知道如何确定X的值是什么.虽然答案是-91.75,但我并不知道它是如何得出的(尽管我知道如何,这需要很长时间才能得出这个答案,而且我不确定我们如何才能快速提出在短时间内解决问题,例如在编写考试时).

在此先感谢您的帮助!

Answer 1

看看这些行：

m = (a + b) / 2
return trace(a, m) + ...

b这些行仅在大于时才会执行a。这意味着m将始终大于a并且第一个递归函数调用具有完全相同的问题。有了值a = 1和b > a，m收敛到1。理论上，递归永远不会结束，因为m永远不会1.0或更少。然而，浮点精度是有限的，因此在某个点（在多次递归调用之后）处理器不能m与1.0. 此时，elif (a == b):变为真并停止递归。这并不能解释为什么结果是-91.75，但它说明了为什么几乎不可能在图表或树或其他东西中显示所有递归调用。我希望它有帮助。