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