Re: Tail recursion and local functions

*To*: mathgroup at smc.vnet.net*Subject*: [mg45705] Re: Tail recursion and local functions*From*: Jens-Peer Kuska <kuska at informatik.uni-leipzig.de>*Date*: Wed, 21 Jan 2004 04:54:50 -0500 (EST)*Organization*: Universitaet Leipzig*References*: <buiv4p$qtn$1@smc.vnet.net>*Reply-to*: kuska at informatik.uni-leipzig.de*Sender*: owner-wri-mathgroup at wolfram.com

Hi, fact3[n_:Integer] := Module[{aux}, aux = Function[{i, acc}, If[i <= 0, acc, aux[i - 1, i acc]]]; aux[n, 1]] work a expected. Regards Jens Matthew McDonnell wrote: > > Hi All, > I have recently been learning a bit of functional programming > using OCaml and was trying to translate tail recursion using auxillary > local functions into Mathematica. > My question is whether Mathematica allows local functions to be > defined within functions, or just local variables? More explanation > follows: > > Consider the function to compute the factorial of n i.e. fact[n]=n! > (not concerned with coping with negative n for the moment, define n! =1 > for negative n) > > Standard recursive solution: > =========================== > fact1[n_:Integer] := If[n <= 0, 1, n fact1[n - 1]]; > > Works, but hits standard recursion limit of 256 for n>253. > > Tail recursive solution: > ======================= > auxFact[n_:Integer, acc_:Integer] := > If[n <= 0, acc, auxFact[n - 1, n acc]]; > fact2[n_:Integer] := auxFact[n, 1]; > > Works, hits the Iteration limit of 4096 for n>2046 > > Tail recursive solution with local auxillary function: > ===================================================== > fact3[n_:Integer] := Module[ > {aux = Function[{i, acc}, If[i <= 0, 1, aux[i - 1, i acc]]]}, > aux[n, 1]] > > Doesn't work eg fact3[100] gives aux[99,100] > > first class variables (eg able to be passed and returned from functions), > is this correct? Or am I just going the wrong way about it? > > Cheers, > Matt