Tail recursion and local functions
- To: mathgroup at smc.vnet.net
- Subject: [mg45694] Tail recursion and local functions
- From: Matthew McDonnell <kebl1405 at herald.ox.ac.uk>
- Date: Tue, 20 Jan 2004 05:08:04 -0500 (EST)
- Organization: Oxford University, England
- Sender: owner-wri-mathgroup at wolfram.com
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