MathGroup Archive 2007

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Better recursive method?

  • To: mathgroup at smc.vnet.net
  • Subject: [mg72922] Re: Better recursive method?
  • From: Jon Harrop <jon at ffconsultancy.com>
  • Date: Thu, 25 Jan 2007 07:03:28 -0500 (EST)
  • References: <eosh0f$9bs$1@smc.vnet.net> <eovfjr$rtf$1@smc.vnet.net>

Johan Grönqvist wrote:
> My kernel quits silently when attempting pi[10000,1], and I would be
> interested in knowing why.

The current Mathematica kernel eats stack space proportional to the number
of recursive calls, limited by $RecursionLimit. Moreover, every stack frame
is about 10x the size of the equivalent stack frame in a compiled language
(e.g. C, OCaml). So you must keep $RecursionLimit low to avoid having your
kernel segfault and die (silently from the GUI) when the OS runs out of
stack space, around $RecursionLimit=10^4. Under Linux, you can also
increase the amount of stack space available to a process using ulimit, but
this just staves off the problem (with current OSs, stack is more limited
than heap).

This is not an inherent or theoretical limitation, just a practical
limitation of the current implementation that may well be fixed at a future
date.

If you're interested in the theory that underpins this problem, have a look
at tail recursion in functional languages and continuation passing style.
Tail recursion is covered in my OCaml book and Appel wrote an excellent
book on compiling with continuations, where he shows how you can
automatically transform a program so that it uses no stack space.

-- 
Dr Jon D Harrop, Flying Frog Consultancy
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists/index.html?usenet


  • Prev by Date: Re: Zeroes of Zeta function
  • Next by Date: Re: pdf
  • Previous by thread: Re: Better recursive method?
  • Next by thread: Wolfram Workbench: SVN & notebook diffs