Re: Tail recursion and local functions

• To: mathgroup at smc.vnet.net
• Subject: [mg45705] Re: Tail recursion and local functions
• From: Jens-Peer Kuska <kuska at informatik.uni-leipzig.de>
• Date: Wed, 21 Jan 2004 04:54:50 -0500 (EST)
• Organization: Universitaet Leipzig
• References: <buiv4p\$qtn\$1@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

```Hi,

fact3[n_:Integer] :=
Module[{aux}, aux = Function[{i, acc}, If[i <= 0, acc, aux[i - 1, i
acc]]];
aux[n, 1]]

work a expected.

Regards
Jens

Matthew McDonnell wrote:
>
> 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

```

• Prev by Date: Re: typesetting fractions
• Next by Date: Re: using functions with package name prefixed.
• Previous by thread: Tail recursion and local functions
• Next by thread: Re: Tail recursion and local functions