14

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

magma
  • 626
  • 5
  • 15
  • That looks tricky in the general case, especially if you have more than one parameter, and the recursion does not strictly decrease them in each step. – Thilo Sep 14 '11 at 10:22
  • 3
    @Thilo If it weren't tricky I would not have asked it :-) – magma Sep 14 '11 at 10:34

2 Answers2

8

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
Leonid Shifrin
  • 22,449
  • 4
  • 68
  • 100
  • That is the part that @magma could "easily imagine". Would be nice if there was a way to figure out how far $RecursionLimit really needs to be raised considering that there are already some memoized values. – Thilo Sep 14 '11 at 10:38
  • @Thilo Please see my edit - based on magma's suggestion (assuming recursion depth as `input - number-of-known-results + const`. If it still exceeds that, my last code has a limit which would tell the user that the computation must be split into several steps. – Leonid Shifrin Sep 14 '11 at 11:00
  • 2
    Since `$RecursionLimit` is only set locally for this function, why not set it to `Infinity` in the `Block` instead of trying to come up with a "big enough" value? The safety problem still remains in any case: have a too deep recursion, and the kernel will crash. I am not aware of any way to determine the largest crash-safe `$RecursionLimit`, if anyone knows one, let me know. – Szabolcs Sep 14 '11 at 12:31
  • @Thilo I would say that recursion can be defined on a restricted class of parzially ordered sets (posets) of inputs. Can't remember its exact name right now. The fact that you have more than one parameter (ie. you work on a cartesian product of suitable posets) is not a problem, since you can use (for example ) lexicographic ordering. Any reasonably defined recursive function must by necessity "decrease" the parameter in each step – magma Sep 14 '11 at 12:37
  • This is an excellent answer! The trick I was looking for was Length[DownValues[..]]. Obvious in retrospect. Silly me :-) – magma Sep 14 '11 at 13:29
  • 1
    @Szabolcs I guess there is no single universal limiting "safe" value for `$RecursionLimit`, since it must be determined by the memory used by the stack, which depends on the problem. My experiments resulted in crashes for `$RecursionLimit` in the range of hundreds thousands. It probably should be possible to have an estimate on the available stack space, although this won't help much. Regardless, I would *never* use `$RecursionLimit = Infinity`, since this is a true recipe for disaster. If possible, one should use tail-recursive (in mma sense) functions to reduce recursion to iteration. – Leonid Shifrin Sep 14 '11 at 13:30
  • 1
    @magma Note that for a large (tens of thousands or more) number of definitions, `DownValues[f]` may take considerable time to execute. If such cases will be frequent, you may want to keep a separate counter (localized inside the same `Module`), which is incremented every time when a new definition is added, to reduce the overhead. – Leonid Shifrin Sep 14 '11 at 13:39
  • One comment and 2 questions. 1 The 10 in the recursionlimit formulae should be at least 20, to avoid $RecursionLimit::limset error, as hinted by @belisarius answer below.2 This Module wrapper trick is shown also in the module page of the doc center, applications section. What is its advantage vs using a direct f definition? 3 why is the x localized in the Module? (Look at the ??f info) – magma Sep 14 '11 at 13:42
  • A localized separate counter updated each time a definition is added, was my original idea. Your Length[DownValues[..]] is more elegant, with all its speed limitations. – magma Sep 14 '11 at 13:47
  • @magma Regarding 20 instead of 10 - good point, I forgot about limset.The `Module` trick is necessary here to keep memoized definitions. If you only use `f`, then I don't see an easy way to have both the main memoized definition `f[x_] := f[x] = f[x - 1] + f[x - 2]` *and* the one that is checking a recursion limit. Perhaps, one can do it, I just found it easier to delegate memoization to another symbol. Regarding `x$` - it is not lolalized in `Module` despite its look, but is a result of `SetDelayed` renaming its pattern variable inside `Module`, to avoid name possible name collisions. – Leonid Shifrin Sep 14 '11 at 13:57
  • @Szabolcs Sorry if my previous comment was re-iterating the obvious. My main message was that I do agree with your main point - the safety problem remains. I just wish we were given more information about the stack use from the system. I actually tried to measure things like `ByteCount[Stack[]]` or `LeafCount[Stack[]]` in my experiments, to see if some univeral limits on these can be found, but did not succeed. – Leonid Shifrin Sep 14 '11 at 15:40
6

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

Dr. belisarius
  • 60,527
  • 15
  • 115
  • 190
  • +1. I was thinking of adding something similar to my answer, but you did it first and perhaps more elegantly than what I intended to do. One may want increase the `$RecursionLimit` step if the overhead of increasing in small steps is too much. – Leonid Shifrin Sep 14 '11 at 13:32
  • @Leonid I guess a coarser step control would require incrementing a variable, or at least meassuring the stack depth. – Dr. belisarius Sep 14 '11 at 13:38
  • Perhaps you are right. I did not give this suggestion much thought, it may be harder to implement well. – Leonid Shifrin Sep 14 '11 at 13:41
  • 1
    This is also a very interesting solution, which uses Block inside Block recursion – magma Sep 14 '11 at 15:22