[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
Prev by Date:
**Re: Tail recursion and local functions**
Next by Date:
**RE: Unexpected behaviour of HoldRest**
Previous by thread:
**Re: Tail recursion and local functions**
Next by thread:
**Re: Tail recursion and local functions**
| |