Re: Tail recursion and local functions

*To*: mathgroup at smc.vnet.net*Subject*: [mg45720] Re: Tail recursion and local functions*From*: Paul Abbott <paul at physics.uwa.edu.au>*Date*: Wed, 21 Jan 2004 04:55:03 -0500 (EST)*Organization*: The University of Western Australia*References*: <buiv4p$qtn$1@smc.vnet.net>*Sender*: owner-wri-mathgroup at wolfram.com

In article <buiv4p$qtn$1 at smc.vnet.net>, Matthew McDonnell <kebl1405 at herald.ox.ac.uk> wrote: > 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. Not sure why you really want or need these in Mathematica. > My question is whether Mathematica allows local functions to be > defined within functions, or just local variables? Mathematica allows local functions to be defined within functions. > 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. You can get around this as follows: fact1[n_:Integer] := Block[{$RecursionLimit = Infinity}, If[n <= 0, 1, n fact1[n - 1]]] Note that you can write $RecursionLimit = Infinity; fac = If[# == 1, 1, # #0[# - 1]] &; > 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 Similarly, you can get around this by setting $IterationLimit = Infinity > 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] Because the code is wrong. It should read fact3[n_:Integer] := Module[ {aux = Function[{i, acc}, If[i <= 0, 1, i aux[i - 1, acc]]]}, aux[n, 1]] > 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 (from your alma mata), Paul -- Paul Abbott Phone: +61 8 9380 2734 School of Physics, M013 Fax: +61 8 9380 1014 The University of Western Australia (CRICOS Provider No 00126G) 35 Stirling Highway Crawley WA 6009 mailto:paul at physics.uwa.edu.au AUSTRALIA http://physics.uwa.edu.au/~paul