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: <email@example.com>
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:= f := 0 In:= f[n_] := 1+f[n-1] In:= f $RecursionLimit::reclim: Recursion depth of 256 exceeded. Out= 255 + Hold[f[746 - 1]] In:= $RecursionLimit=Infinity Out= Infinity In:= f Out= 1000 In:= f Out= 10000 In:= f 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