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

如果我甚至不缓存结果，为什么算法的执行时间会有很大差异？为什么索引的递增顺序会影响执行时间？

- rfrm

---

是的，这就是动态规划的工作原理（这是动态规划的一个示例，您从目标状态开始向后工作，从而可以跳过会导致无效解决方案的计算）...但是如果您从初始状态开始，它需要进行全面搜索，并且在计算后才知道答案是否无效。 - Joran Beasley

@rfrm，“@measure” 是从哪里来的？ - Jan Vlcinsky

这只是一个计时装饰器，我相信 @JanVlcinsky。 - Joran Beasley

通话数量取决于输入顺序。您可以通过在 countChange 中按降序对列表进行排序来获得最小数量。coin_list.sort(reverse=True)。 - Sean Fujiwara

@JoranBeasley：从“目标状态”开始向后推导到“起始状态”并不会自动使算法变得“动态”。假设我有一个迷宫，里面恰好有两扇门，A和B。你告诉我，如果我将A标记为“进入”，B标记为“退出”，并且你从B开始，那么你正在进行某种“动态规划”迷宫求解？如果我交换标签，使A读作“退出”，B读作“进入”，那么我的迷宫求解器突然就不再是动态的了吗？ - John Y

Answer 1

根据我的理解，这与动态规划没有关系。仅仅是反转索引并不能让它变得“动态”。

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

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

就像某些排序算法在处理已排序的数据时非常快，而在处理反转的数据时非常慢一样，你在这里得到了那种类型的算法。

当输入是递增的时候，countChange 需要更多的迭代才能得出最终答案，因此看起来要慢得多。然而，当输入是递减的时候，性能特征就会颠倒过来。

- John Y

---

它确实可以使用动态编程解决这个问题，因为反转它可以避免探索无效路径。它还确保您只计算每个子问题一次...（所有相同的+1，因为是的，它运行较慢的原因是它调用更多次...） - Joran Beasley

@JoranBeasley：我认为你真的误解了动态规划。要么你没有花时间研究这个问题的属性。请看我的编辑。 - John Y

你说得对...我还不确定...我以为我理解了动态规划，现在我开始怀疑自己了（而且我也没有真正检查过 OP 使用的算法...它看起来像是很多东西都被重新计算了...无论顺序如何）... - Joran Beasley

Answer 2

三位数字的组合并不是很多。

原因在于，向前探索时您必须探索每种可能性，但是当您向后探索时，可以消除大量无效解决方案，而无需实际计算它们。

向前探索需要调用500k次count函数。

向后探索时，您的代码仅调用30k次count函数...

通过记忆化调用（或更改算法以避免重复调用），您可以使这两者都更快。

- Joran Beasley

---

动态规划需要保存先前的结果，但是你可以看到，我没有保存任何东西。 - rfrm

不，它通常是递归调用的（尽管没有强制要求，这只是最直观的方式）...就像你现在正在做的一样...这就是动态规划，也是为什么从起始状态开始比从目标状态开始要慢得多的原因...（事实上，我写的教程就是这个完全相同的问题陈述）。 - Joran Beasley

将其反转可以避免探索无效路径。@Joran，这很有道理，谢谢。 - rfrm

这不是动态规划。动态规划基本上是将问题分解成重叠的子问题，并重复使用子问题计算的结果。在这里没有重复使用任何东西；事实上，在两个版本中，count都会以相同的参数重复调用。John Y的答案更准确。 - user2357112

你的动态规划教程甚至没有使用动态规划。你的教程中所使用的是非动态递归方法；需要进行记忆化才能使其变得动态。 - user2357112