Tail recursion and local functions

*To*: mathgroup at smc.vnet.net*Subject*: [mg45694] Tail recursion and local functions*From*: Matthew McDonnell <kebl1405 at herald.ox.ac.uk>*Date*: Tue, 20 Jan 2004 05:08:04 -0500 (EST)*Organization*: Oxford University, England*Sender*: owner-wri-mathgroup at wolfram.com

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