wolfram-mathematica - 内存递归函数。如何让他们万无一失？

Question

内存函数是记住它们找到的值的函数。
如有必要，请在文档中心查看有关 Mathematica 的一些背景知识。

假设您有以下定义

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

在您的一个包裹中。用户可以加载包并立即开始询问 f[1000]。
这将触发 $RecursionLimit::reclim 错误消息并中止。
即使用户然后尝试更小的东西，比如 f[20]，到现在 f 的定义已经损坏并且结果不再好。当然包开发人员可能会增加递归限制并警告用户，但我的问题是:

您如何改进 f 定义，以便如果用户要求 f[1000] 他/她可以毫无问题地得到答案？我对捕获用户输入的方法感兴趣，对其进行分析并采取任何必要的步骤来评估 f[1000]。

我可以很容易地想象，如果输入超过 255(然后将其恢复到原始级别)，则可以更改递归限制，但我真正想看到的是，如果 f 有办法找到找出它“知道”多少个值(fknownvalues)并接受任何输入 <=fknownvalues+$RecursionLimit 没有问题，或者如果输入更高，则增加 $RecursionLimit。

感谢您的帮助

Answer 1

下面的代码假设您可以从输入参数的值确定 $RecursionLimit 的值:

Clear[f];
Module[{ff},
  ff[0] = ff[1] = 1;
  ff[x_] := ff[x] = ff[x - 1] + ff[x - 2];

  f[x_Integer] :=f[x] =
     Block[{$RecursionLimit = x + 5},
        ff[x]
  ]]

我正在使用本地函数 ff 来完成主要工作，而 f 只是调用它包装在 Block 中，并为 $RecursionLimit 提供适当的值:

In[1552]:= f[1000]
Out[1552]=  7033036771142281582183525487718354977018126983635873274260490508715453711819693357974224
9494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125
598767690091902245245323403501  

编辑

如果您想更精确地设置 $RecursionLimit ，您可以将上面的代码部分修改为:

f[x_Integer] :=
  f[x] =
    Block[{$RecursionLimit = x - Length[DownValues[ff]] + 10},
    Print["Current $RecursionLimit: ", $RecursionLimit];
    ff[x]]]

Print 语句用于说明。 10 的值相当随意——要获得它的下限，必须计算必要的递归深度，并考虑到已知结果的数量是 Length[DownValues[ff]] - 2(因为 ff 有 2 个通用定义)。下面是一些用法:

In[1567]:= f[500]//Short

During evaluation of In[1567]:= Current $RecursionLimit: 507
Out[1567]//Short= 22559151616193633087251269<<53>>83405015987052796968498626

In[1568]:= f[800]//Short

During evaluation of In[1568]:= Current $RecursionLimit: 308
Out[1568]//Short= 11210238130165701975392213<<116>>44406006693244742562963426

如果您还想限制可能的最大 $RecursionLimit，这也很容易按照相同的思路进行。例如，在这里，我们将其限制为 10000(同样，这在 Module 中):

f::tooLarge = 
"The parameter value `1` is too large for single recursive step. \
Try building the result incrementally";
f[x_Integer] :=
   With[{reclim = x - Length[DownValues[ff]] + 10},
     (f[x] =
        Block[{$RecursionLimit = reclim },
        Print["Current $RecursionLimit: ", $RecursionLimit];
        ff[x]]) /; reclim < 10000];

f[x_Integer] := "" /; Message[f::tooLarge, x]]

例如:

In[1581]:= f[11000]//Short

During evaluation of In[1581]:= f::tooLarge: The parameter value 11000 is too 
large for single recursive step. Try building the result incrementally
Out[1581]//Short= f[11000]

In[1582]:= 
f[9000];
f[11000]//Short

During evaluation of In[1582]:= Current $RecursionLimit: 9007
During evaluation of In[1582]:= Current $RecursionLimit: 2008
Out[1583]//Short= 5291092912053548874786829<<2248>>91481844337702018068766626