12

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

4

14 回答 14

22

它们不是相互排斥的。你可以同时使用它们。

就个人而言，我会先构建基本递归函数，然后添加记忆，作为优化步骤。

于 2009-01-26T15:17:03.000 回答
13

使用的经验法则是基于子问题的重叠量。如果您正在计算斐波那契数（经典递归示例），那么如果您使用递归，则会进行很多不必要的重新计算。

比如计算F(4)，我需要知道F(3)和F(2)，所以我通过计算F(2)和F(1)来计算F(3)，以此类推。如果我使用递归，我只需计算 F(2) 和大多数其他 F(n) 两次。如果我使用 memoization，我可以查找值。

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

于 2009-01-26T15:30:28.277 回答
8

递归具有与创建堆栈帧相关的性能损失，memoization 的损失是结果的缓存，如果性能是一个问题，唯一确定的方法是在您的应用程序中进行测试。

在我个人看来，我会首先使用最容易使用和理解的方法，我认为这是递归。直到你证明需要记忆。

于 2009-01-26T15:14:14.393 回答
7

记忆化只是一种缓存方法，恰好经常用于优化递归。它不能代替递归。

于 2009-01-27T22:53:12.500 回答
6

不确定我可以在不知道问题的情况下说。通常你会想要使用递归的记忆。尽管如此，如果您实际上可以将它用作替代解决方案，那么记忆化可能比递归快得多。它们都有性能问题，但随着问题的性质/输入的大小而有所不同。

于 2009-01-26T15:14:42.007 回答
3

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

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

于 2009-01-26T15:15:21.850 回答
3

我相信您可能会将记忆化（正如其他人所指出的那样，递归算法的优化策略）与动态编程（模拟递归解决方案但实际上不使用递归）混淆。如果这是您的问题，我会说这取决于您的优先级：高运行时效率（动态编程）或高可读性（记忆，因为问题的递归解决方案仍然存在于代码中）。

于 2009-02-09T23:57:33.830 回答
2

这取决于你要做什么。动态编程（记忆）几乎总是更快。通常很多。（即三次方到平方，或指数到多边形），但根据我的经验，递归更容易阅读和调试。

话又说回来，很多人像瘟疫一样避免递归，所以他们觉得它不容易阅读......

另外，（第三手？）我发现在提出递归解决方案之后最容易找到动态解决方案，所以我最终都做了。但如果您已经拥有这两种解决方案，Dynamic 可能是您最好的选择。

我不确定我是否有帮助，但你去吧。与算法选择的许多事情一样，YMMV。

于 2009-01-26T15:16:44.560 回答
2

如果你的问题是递归问题，除了递归你还有什么选择？

您可以使用记忆以短路的方式编写递归函数，以获得第二次调用的最大速度。

于 2009-01-26T15:19:32.917 回答
2

我不同意 Tomalak 的断言，即对于递归问题，你别无选择，只能递归？

最好的例子就是上面提到的斐波那契数列。在我的计算机上，F(45) 的递归版本（F 表示斐波那契）需要 15 秒来进行 2269806339 次加法，迭代版本需要 43 次加法并在几微秒内执行。

另一个著名的例子是河内塔。在您上完该主题的课程之后，似乎递归是解决该问题的唯一方法。但即使在这里也有一个迭代解决方案，尽管它不像递归解决方案那么明显。即便如此，迭代速度更快，主要是因为不需要昂贵的堆栈操作。

如果您对塔的非递归版本感兴趣，这里是 Delphi 源代码：

procedure TForm1.TowersOfHanoi(Ndisks: Word);
var
  I: LongWord;
begin
  for I := 1 to (1 shl Ndisks) do
    Memo1.Lines.Add(Format('%4d: move from pole %d to pole %d',
      [I, (I and (I - 1)) mod 3, (I or (I - 1) + 1) mod 3]));
  Memo1.Lines.Add('done')
end;
于 2009-02-13T16:17:47.560 回答
1

如果可以使用尾递归技术解决问题，则递归不需要使用大量堆栈空间。如前所述，取决于问题。

于 2009-01-26T15:20:46.720 回答
1

在通常情况下，您面临两个有助于您做出决定的标准：

  • 运行
  • 可读性

递归代码通常速度较慢，但​​可读性更高（并非总是如此，但最常见的是。正如所说，如果您的语言支持尾递归，它会有所帮助 - 如果不支持，那么您无能为力）。

递归问题的迭代版本通常在运行时更快，但代码很难理解，因此很脆弱。

如果两个版本具有相同的运行时间和相同的可读性，则没有理由选择其中一个。在这种情况下，您必须检查其他事项：此代码会更改吗？怎么保养？您对递归算法感到满意还是它们让您做噩梦？

于 2009-01-26T15:50:25.413 回答
1 
var memoizer = function (fund, memo) {
    var shell = function (arg) {
        if (typeof memo[arg] !== 'number') {
            memo[arg] = fund(shell, arg);
        }
        return memo[arg];
    };
    return shell;
};

var fibonacci = memoizer(function (recur, n) { return recur(n - 1) + recur(n - 2); }, [0, 1]);

两者都用！

于 2009-02-09T20:19:42.967 回答
0

将两者结合起来。通过使用记忆优化您的递归解决方案。这就是记忆的意义所在。用于使用内存空间来加速递归。

于 2011-02-20T01:02:19.223 回答