Re: Recursion limit: a good idea to ignore?
- To: mathgroup at smc.vnet.net
- Subject: [mg82228] Re: Recursion limit: a good idea to ignore?
- From: Jon Harrop <jon at ffconsultancy.com>
- Date: Tue, 16 Oct 2007 03:16:45 -0400 (EDT)
- References: <feutsm$st$1@smc.vnet.net>
Will Robertson wrote:
> I've written a potentially inefficient algorithm to combine multiple
> joined polygons into a single one. On large plots I get the warning
> "$RecursionLimit::reclim: Recursion depth of 256 exceeded." and a
> bunch of errors because of this.
>
> Now, should I try and re-write my program (the speed of it is not
> entirely critical) to avoid recursion or is it "okay" to locally
> remove the recursion limit for such code?
Deep recursion is often a bad idea. In Mathematica code, it is an even worse
idea that usual.
The following excerpt demonstrates unbounded recursion that eventually
results in a Segmentation Fault (on AMD64 Debian Linux):
$ MathKernel
Mathematica 5.1 for Linux x86 (64 bit)
Copyright 1988-2004 Wolfram Research, Inc.
-- Motif graphics initialized --
In[1]:= f[0] := 0
In[2]:= f[n_] := 1+f[n-1]
In[3]:= f[1000]
$RecursionLimit::reclim: Recursion depth of 256 exceeded.
Out[3]= 255 + Hold[f[746 - 1]]
In[4]:= $RecursionLimit=Infinity
Out[4]= Infinity
In[5]:= f[1000]
Out[5]= 1000
In[6]:= f[10000]
Out[6]= 10000
In[7]:= f[100000]
Segmentation fault
So recursing too deep (applying your function to a large problem) can cause
the whole Mathematica kernel to die when it overruns the system stack.
The term rewriter at the core of Mathematica is a very powerful and
general-purpose evaluator that requires much bigger stack frames when it
recurses compared to most other languages. So Mathematica code is more
prone to this problem than most other languages.
For example, the equivalent OCaml code:
$ ocamlnat
Objective Caml version 3.10.0 - native toplevel
# let rec f = function
| 0 -> 0
| n -> 1 + f(n - 1);;
val f : int -> int = <fun>
# f 1000;;
- : int = 1000
# f 10000;;
- : int = 10000
# f 100000;;
- : int = 100000
# f 1000000;;
Stack overflow during evaluation (looping recursion?).
#
Note that OCaml recursed ~10x deeper before failing and failed with a nice
catchable exception.
In the language zoo, there are some notable exceptions that do not suffer
from this problem. The SML/NJ compiler is one of the most famous examples.
Before compiling code, it rearranges all function calls into continuation
passing style (CPS) so that they consume heap space rather than the (far
more limited) system stack space.
I have not studied Mathematica's implementation of tail recursion in detail
so I cannot say whether or not performing such a transformation will help
you here. You might ask Wolfram Research about it.
The solution to your problem is to avoid recursive function calls that
consume stack space. This typically entails either rewriting the offending
function in tail recursive form, or rewriting it in imperative form.
--
Dr Jon D Harrop, Flying Frog Consultancy
http://www.ffconsultancy.com/products/?u