斐波那契数列的性能表现

Question

f[0] = 0;
f[1] = 1;
f[x_] := f[x-1] + f[x-2]

这个函数在Mathematica中运行缓慢，我需要提高它的速度。我必须使用函数式编程和递归。我不确定为什么它运行得如此缓慢，即使是最微小的改进想法也会有所帮助。

- Jon

---

我不是数学大师，但你为什么要使用两个不同的变量？ - josh.trow

请查看教程：http://reference.wolfram.com/mathematica/tutorial/FunctionsThatRememberValuesTheyHaveFound.html - Simon

@dreeves：" 作业标签，就像其他所谓的“元”标签一样，现在被不鼓励使用，"但是@Jon，请（像往常一样）遵循通用指南，说明任何特殊限制，展示你已经尝试过什么，并询问具体让你困惑的事情。 - Roger Pate

Answer 1

一个写更快的递归函数的好方法是让它记住先前的值。当然，这样做会消耗内存，但在某些情况下确实有帮助。为了计算 f[x]，你需要计算 f[x-1] 和 f[x-2] - 然后为了计算 f[x-1]，你又要重新计算 f[x-2]；你最终会重复计算很多次的值。(请原谅我的不精准！)

为了在计算中存储值，请使用这个惯用法：

f[x_] := ( f[x] = (* calculation of f[x] goes here *)  )

编辑：我在这台机器上没有Mathematica，但我非常确定这个计算不会出错。

f[0] = 0;
f[1] = 1;
f[x_] := ( f[x] = f[x-1] + f[x-2] );

f[256]

如我在下面的评论中所说，如果您有其他关于f的定义，您可能需要使用Clear[f]清除它们。

感谢rcollyer：请注意$RecursionLimit！默认值为256。（当然，这是有充分理由的。非常深的递归通常不是一个好主意。）

- Cascabel

---

f[x_] := f[x] = f[x-1] + f[x-2] 但这个不起作用，你是这个意思吗？ - Jon

@Jon：我忘记你是否需要任何括号，但是是的。确保不要忘记你的基本情况！如果你搞砸了并尝试使用它，你可能会存储错误的结果 - 你可能需要在再次尝试之前清除[f]来修复它。 - Cascabel

@rcollyer：谢谢。我很确定我不需要它们，但在“计算出错误的值”之后，我变得有点神经质了。 - Cascabel

@Jon，我突然想到这个问题了，你用的x的初始值是多少？还有，你有遇到什么错误吗？如果把x的初始值设为x = 1000，我就会遇到“递归深度超过256”的错误。 - rcollyer

@rcollyer：哦，对了，我应该想到那个的。天啊，我太生疏了。你可以设置变量$RecursionLimit，或者（感谢记忆化）通过类似于Do[f[x],{x,0,1024,256}]的方式逐步逼近它。 - Cascabel

这个三元组：f[0] = 0; f[1] = 1; f[x_] := f[x] = f[x - 1] + f[x - 2] 运行良好。 f[256] 在可忽略的时间内产生正确的数字 141693817714056513234709965875411919657707794958199867，而 ??f 显示了 f 的所有 257 个备忘录点值。 - Reb.Cabin

Answer 2

Jefromi是正确的。在维基百科上查看记忆化。他们使用阶乘的例子来说明如何通过记忆化加速它。

- Bradley Kreider

Answer 3

记忆化 是编写更快的递归函数的好方法。然而，在这种情况下，有一种递归替代方案比原始函数运行得更快，而且不需要记忆化。

关键观察是看到原始定义执行了大量重复计算。考虑如果我们计算fib[4]会发生什么：

fib[4] = fib[3] + fib[2]
  fib[3] = fib[2] + fib[1]
    fib[2] = fib[1] + fib[0]
      fib[1] = 1
      fib[0] = 1
    ∴ fib[2] = 1 + 1 = 2
    fib[1] = 1
  ∴ fib[3] = 2 + 1 = 3
  fib[2] = fib[1] + fib[0]
    fib[1] = 1
    fib[0] = 1
  ∴ fib[2] = 1 + 1 = 2
∴ fib[4] = 2 + 1 = 3

在这个过程中，fib[2]和fib[0]各被计算了两次，而fib[1]被计算了三次。对于更大的计算，浪费会急剧增长--事实上是指数级别的。

如果一个人要手动计算相同的斐波那契数列，可能会像这样进行：

0: given   0
1: given   1
2: 0 + 1 = 1
3: 1 + 1 = 2
4: 1 + 2 = 3

没有冗余计算。在任何给定点，只需要考虑前两个结果。这种方法可以通过递归表达。

fib2[0] = 0;
fib2[n_] :=
  Module[{f},
    f[n, p1_, _] := p1;
    f[x_, p1_, p2_] := f[x + 1, p1 + p2, p1];
    f[1, 1, 0]
  ]

Block[{$IterationLimit = Infinity}, fib2[100000]]

毫无疑问，这种形式不如原始代码易于阅读。另一方面，原始函数在我的计算机上计算 fib[35] 需要35秒，而修订后的函数在相同情况下运行时间报告为零。此外，修订后的函数在0.281秒内计算出fib2[100000]，而不需要任何记忆化的额外存储空间。原始函数无法计算出 fib[100000]，而 记忆化版本 会使我的 Mathematica 7.01 内核崩溃--可能是因为记忆化规则太多了吧？

请注意，默认情况下，Mathematica 不会迭代一个函数超过4096次。要提高限制，您必须像上面的示例一样将更高的值分配给 $IterationLimit。

当然，在 Mathematica 中，有很多非递归的方法来计算斐波那契数列，包括内置的 Fibonacci 函数。但这不是这个练习的重点。

尾调用优化呢？

使用尾递归来表达递归函数总是可取的。这允许递归通过简单的迭代执行，而无需在堆栈上保留中间结果的开销。fib2是尾递归的。一些语言，如Scheme，要求尾调用优化。其他语言，如Java，可以支持它，但不支持（或不愿意，比如Python）。

在Mathematica的情况下，尾调用优化的程度还不清楚。有关此点的进一步讨论，请参见另一个SO问题。

- WReach