斐波那契的表现

Question

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

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

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。（当然，这是有充分理由的。真正的深度递归通常不是一个好主意。）

Answer 2

杰弗罗米是对的。查看维基百科上的Memoization。他们使用阶乘的例子以及如何通过记忆来加速它。

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]]

毫无疑问，这种形式不如原始形式那么容易阅读。另一方面，原始函数在我的机器上花了 35 秒来计算 fib[35]，而修改后的函数的运行时间报告为零。此外，修改后的函数在 0.281 秒内计算出 fib2[100000]，无需任何额外的记忆存储。 fib[100000] 超出了原始函数的范围，并且 记忆版本使我的 Mathematica 7.01 内核崩溃——也许记忆规则太多？

请注意，默认情况下，Mathematica 迭代函数的次数不超过 4096 次。要提高该限制，您必须为 $IterationLimit 指定一个更高的值，如上例所示。

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

尾部调用优化？

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

就 Mathematica 而言，尚不清楚尾调用优化执行到什么程度。有关这一点的进一步讨论，请参阅另一个SO问题。