Memoized recursive functions. How to make them fool-proof?

Question

Memoized functions are functions which remember values they have found. Look in the doc center for some background on this in Mathematica, if necessary.

Suppose you have the following definition

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

in one of your packages. A user may load the package and start asking right away f[1000]. This will trigger a $RecursionLimit::reclim error message and abort. Even if the user then tries something smaller, say f[20], by now the definition of f is corrupt and the result is not good anymore.Of course the package developer might increase the recursion limit and warn the user, but my question is:

How can you improve the f definition so that if the user asks for f[1000] he/she gets the answer without any problem? I am interested in a way to trap the user input, analyze it and take whatever steps are necessary to evaluate f[1000].

I can easily imagine that one can change the recursion limit if the input is more than 255 (and then bring it back to the original level), but what I would really like to see is, if there is a way for the f to find out how many values it "knows" (fknownvalues) and accept any input <=fknownvalues+$RecursionLimit without problems or increase the $RecursionLimit if the input is higher.

Thank you for your help

Answer 1

Here is the code assuming that you can determine a value of $RecursionLimit from the value of the input argument:

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

I am using a local function ff to do the main work, while f just calls it wrapped in Block with a proper value for $RecursionLimit:

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

EDIT

If you want to be more precise with the setting of $RecursionLimit, you can modify the part of the code above as:

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

The Print statement is here for illustration. The value 10 is rather arbitrary - to get a lower bound on it, one has to compute the necessary depth of recursion, and take into account that the number of known results is Length[DownValues[ff]] - 2 (since ff has 2 general definitions). Here is some usage:

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

If you also want to limit the maximal $RecursionLimit possible, this is also easy to do, along the same lines. Here, for example, we will limit it to 10000 (again, this goes inside 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]]

For example:

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

A slight modification on Leonid's code. I guess I should post it as a comment, but the lack of comment formatting makes it impossible.

Self adaptive Recursion Limit

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
*)

Edit

Trying to set $RecursionLimit sparsely:

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

Not sure how useful it is ...