[Date Index] [Thread Index] [Author Index]

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