Re: Tail recursion and local functions
- To: mathgroup at smc.vnet.net
- Subject: [mg45720] Re: Tail recursion and local functions
- From: Paul Abbott <paul at physics.uwa.edu.au>
- Date: Wed, 21 Jan 2004 04:55:03 -0500 (EST)
- Organization: The University of Western Australia
- References: <buiv4p$qtn$1@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
In article <buiv4p$qtn$1 at smc.vnet.net>,
Matthew McDonnell <kebl1405 at herald.ox.ac.uk> wrote:
> 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.
Not sure why you really want or need these in Mathematica.
> My question is whether Mathematica allows local functions to be
> defined within functions, or just local variables?
Mathematica allows local functions to be defined within functions.
> 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.
You can get around this as follows:
fact1[n_:Integer] := Block[{$RecursionLimit = Infinity},
If[n <= 0, 1, n fact1[n - 1]]]
Note that you can write
$RecursionLimit = Infinity;
fac = If[# == 1, 1, # #0[# - 1]] &;
> 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
Similarly, you can get around this by setting
$IterationLimit = Infinity
> 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]
Because the code is wrong. It should read
fact3[n_:Integer] := Module[
{aux = Function[{i, acc}, If[i <= 0, 1, i aux[i - 1, acc]]]},
aux[n, 1]]
> 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 (from your alma mata),
Paul
--
Paul Abbott Phone: +61 8 9380 2734
School of Physics, M013 Fax: +61 8 9380 1014
The University of Western Australia (CRICOS Provider No 00126G)
35 Stirling Highway
Crawley WA 6009 mailto:paul at physics.uwa.edu.au
AUSTRALIA http://physics.uwa.edu.au/~paul