RE: Tail recursion and local functions
- To: mathgroup at smc.vnet.net
- Subject: [mg45709] RE: [mg45694] Tail recursion and local functions
- From: "Wolf, Hartmut" <Hartmut.Wolf at t-systems.com>
- Date: Wed, 21 Jan 2004 04:54:53 -0500 (EST)
- Sender: owner-wri-mathgroup at wolfram.com
>-----Original Message----- >From: Matthew McDonnell [mailto:kebl1405 at herald.ox.ac.uk] To: mathgroup at smc.vnet.net >Sent: Tuesday, January 20, 2004 11:08 AM >To: mathgroup at smc.vnet.net >Subject: [mg45709] [mg45694] Tail recursion and local functions > > >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 > No, Matt, apart from the obvious typo, this doesn't work (as perhaps suspected from the result: where does global variable aux come from?) Recognizing something peculiar, Module/Function scoping rename aux from Module to aux$ (not to aux$56 e.g.) but at this place (declaration of local aux) aux from the body of the function refers to global aux. You can avoid this delaying the definition: In[33]:= fact3X[n_:Integer] := Module[{aux}, aux = Function[{i, acc}, If[i <= 0, acc, aux[i - 1, i acc]]]; aux[n, 1]] In[34]:= fact3X[10] Out[34]= 3628800 It works however for Block (and this should not surprise): In[29]:= fact3B[n_:Integer] := Block[{aux = Function[{i, acc}, If[i <= 0, acc, aux[i - 1, i acc]]]}, aux[n, 1]] In[30]:= fact3B[10] Out[30]= 3628800 Perhaps you are interested in this pure function construct: In[42]:= fact3P[n_Integer] := If[#1 <= 1, #2, #0[#1 - 1, #1 #2]] &[n, 1] In[43]:= fact3P[10] Out[43]= 3628800 All these are $IterationLimit-ed. -- Hartmut Wolf