记忆递归函数.如何让他们万无一失？

Question

记忆功能是记住他们发现的值的功能.如有必要,请在文档中心查看Mathematica中的一些背景知识.

假设您有以下定义

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

在你的一个包中.用户可以加载包并立即开始询问f [1000].这将触发$ RecursionLimit :: reclim错误消息并中止.即使用户然后尝试更小的东西,说F [20],现在f的定义是腐败的结果并不好anymore.Of课程包开发者可能会增加递归限制和警告用户,但我的问题是:

如何改进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

Answer 2

对Leonid的代码略有修改.我想我应该将其作为评论发布,但缺乏评论格式使其无法实现.

自适应递归限制

Clear[f];
$RecursionLimit = 20;
Module[{ff},
 ff[0] = ff[1] = 1;
 ff[x_] := 
  ff[x] = Block[{$RecursionLimit = $RecursionLimit + 2},  ff[x - 1] + ff[x - 2]];
 f[x_Integer] := f[x] = ff[x]]

f[30]
(*
-> 1346269
*)

$RecursionLimit
(*
-> 20
*)

编辑

试图稀疏地设置$ RecursionLimit:

Clear[f];
$RecursionLimit = 20;
Module[{ff}, ff[0] = ff[1] = 1;
 ff[x_] := ff[x] =
   Block[{$RecursionLimit =
      If[Length@Stack[] > $RecursionLimit - 5, $RecursionLimit + 5, $RecursionLimit]}, 
       ff[x - 1] + ff[x - 2]];
 f[x_Integer] := f[x] = ff[x]]  

不确定它有多有用......