python - 为什么在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

据我了解，这实际上与动态规划没有任何关系。仅仅反转索引不应该使某些东西变得“动态”。

发生的事情是算法输入敏感。尝试以相反的顺序输入。例如，

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

正如一些排序算法对已经排序的数据非常快而对反向数据非常慢一样，你在这里有那种算法。

在输入增加的情况下，countChange 需要更多的迭代才能得出最终答案，因此看起来要慢很多。然而，当输入减少时，性能特征会发生逆转。