我应该对算法使用递归或memoization吗？

Question

如果我可以选择使用递归或memoization来解决我应该使用的问题？换句话说,如果它们都是可行的解决方案,因为它们提供了正确的输出,并且可以在我正在使用的代码中合理地表达,何时我会使用另一个？

Answer 1

它们不是相互排斥的.你可以使用它们.

就个人而言,我首先构建基本递归函数,然后添加memoization作为优化步骤.

Answer 2

使用的经验法则是基于子问题的重叠量.如果你正在计算斐波纳契数(经典的递归例子),那么如果使用递归就会进行大量不必要的重新计算.

例如,要计算F(4),我需要知道F(3)和F(2),所以我通过计算F(2)和F(1)来计算F(3),依此类推.如果我使用递归,我只计算了F(2)和大多数其他F(n)两次.如果我使用memoization,我可以看看值.

如果您正在进行二分查找,则子问题之间没有重叠,因此递归是可以的.在每个步骤将输入数组拆分成两半会产生两个唯一的数组,它们代表两个没有重叠的子问题.在这种情况下,记忆不会带来好处.

Answer 3

递归具有与堆栈帧的创建相关联的性能损失,memoization的惩罚是结果的缓存,如果性能是关注的唯一方式,则确定将在您的应用程序中进行测试.

在我个人看来,我会先使用最容易使用和理解的方法,在我看来是递归.直到你证明需要进行记忆.

Answer 4

Memoization只是一种恰好用于优化递归的缓存方法.它不能取代递归.

Answer 5

我不知道在不知道问题的情况下我可以说.通常你会想要使用带有递归的memoization .如果您实际上可以将其用作替代解决方案,那么记忆可能比递归明显更快.它们都存在性能问题,但它们随着问题的性质/输入的大小而有所不同.

Answer 6

我选择记忆是因为通常可以访问比堆栈内存更多的堆内存。

也就是说，如果您的算法在大量数据上运行，则在大多数语言中，在用完保存数据的堆上的空间之前，您将用完递归的堆栈空间。