在处理递归函数时如何提高（mathematica）性能？

背景。我想打印 31^(1/2) 的收敛表。我对该表做了以下递归定义。 （将 31^(1/2) 与黄金比例交换，下表将包含斐波那契数列）。

 cf := ContinuedFraction
 tf := TableForm
 p[-1] = 0; p[0] = 1; q[-1] = 1; q[0] = 0;
 a[k_] := cf[Sqrt[31], k][[k]]
 p[k_] := a[k]*p[k - 1] + p[k - 2]
 q[k_] := a[k]*q[k - 1] + q[k - 2]
 s[n_] := Timing[Table[{k, a[k], p[k], q[k]}, {k, 8, 8 n, 8}]] // tf

时间呈指数级快速增长。我必须按alt+。 （中止）s[4]。

问题：处理递归函数时如何提高（mathematica）性能？

从快速（不彻底，承认这一点）看你的代码，它看起来像p and q递归地定义为two以前的值。这意味着要计算n的价值p, ~2^n需要进行评估（每一步都会使数量加倍）。所以，是的，无论使用 Mathematica 或任何其他语言，复杂性都是指数级的。

如果您坚持使用问题的递归公式（例如为了简单起见），那么减少性能损失的最简单方法是使用记忆化 http://en.wikipedia.org/wiki/Memoization，即做类似的事情

p[k_] := p[k] = a[k]*p[k - 1] + p[k - 2]

别忘了Clear[p]在任何重新定义之前。

简而言之，记忆化意味着让函数记住每个输入的计算结果，因此后续计算速度更快。计算起来很可能更快，但也更复杂two来自前两个值（p_(n) 和 p_(n-1)）的值（p_(n+1) 和 p_(n)），则复杂度将是线性的而不是指数的。

_{I hope this helps. I don't have Mathematica here to test right now.}