为什么在Python中，反向递归执行速度比正向递归更快

Question

我写了一个用Python编写的算法，用来计算用不同面额的硬币凑成一定金额的方法有多少种：

@measure
def countChange(n, coin_list):
    maxIndex = len(coin_list)
    def count(n, current_index):        
        if n>0 and maxIndex>current_index:
            c = 0
            current = coin_list[current_index]
            max_coeff = int(n/current)      
            for coeff in range(max_coeff+1):
                c+=count(n-coeff*current, current_index+1)
        elif n==0: return 1
        else: return 0
        return c
    return count(n, 0)

我的算法使用一个索引来获取硬币的面额，正如你所看到的，我的索引在每次进入一个新的调用栈时是逐渐增加的。我意识到这个算法也可以这样写：

@measure
def countChange2(n, coin_list):
    maxIndex = len(coin_list)
    def count(n, current_index):        
        if n>0 and 0<=current_index:
            c = 0
            current = coin_list[current_index]
            max_coeff = int(n/current)      
            for coeff in range(max_coeff+1):
                c+=count(n-coeff*current, current_index-1)
        elif n==0: return 1
        else: return 0
        return c
    return count(n, maxIndex-1)

这次，索引在每次进入一个新的调用栈时是逐渐减少的。我比较了这两个函数的执行时间，发现它们之间有很大的差别：

print(countChange(30, range(1, 31)))
print(countChange2(30, range(1, 31)))

>> Call to countChange took 0.9956174254208345 secods.
>> Call to countChange2 took 0.037631815734429974 secods.

为什么这两个算法的执行时间差别这么大，即使我并没有缓存结果呢？索引的增加顺序为什么会影响执行时间？

Answer 1

三个数字的组合并不多。

原因是，当你向前探索时，你需要考虑每一种可能性；但是当你向后推导时，你可以不计算就排除掉很多无效的解。

向前推算时，你的代码会调用计数函数500,000次。

而向后推算时，你的代码只需要调用计数函数30,000次……

你可以通过记忆化调用（也就是保存之前的结果）来加快这两个过程，或者改变你的算法，避免重复调用。

Answer 2

这其实和动态规划没什么关系，按照我的理解。单纯地反转索引并不会让东西变得“动态”。

这里发生的事情是这个算法对输入非常“敏感”。你可以试着把输入反过来给它。例如，

print(countChange(30, list(reversed(range(1, 31)))))
print(countChange2(30, list(reversed(range(1, 31)))))

就像有些排序算法在处理已经排好序的数据时非常快，而在处理反向排序的数据时却很慢，这里也是这种情况。

当输入是递增的时候，countChange 需要更多的迭代才能得到最终的答案，所以看起来就慢很多。然而，当输入是递减的时候，性能特点就反过来了。