       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 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:= fact3X[n_:Integer] :=
Module[{aux}, aux = Function[{i, acc}, If[i <= 0, acc, aux[i - 1, i
acc]]];
aux[n, 1]]

In:= fact3X
Out= 3628800

It works however for Block (and this should not surprise):

In:= fact3B[n_:Integer] :=
Block[{aux = Function[{i, acc}, If[i <= 0, acc, aux[i - 1, i acc]]]},
aux[n, 1]]

In:= fact3B
Out= 3628800

Perhaps you are interested in this pure function construct:

In:= fact3P[n_Integer] := If[#1 <= 1, #2, #0[#1 - 1, #1 #2]] &[n, 1]

In:= fact3P
Out= 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