Re: Tail recursion and local functions
- To: mathgroup at smc.vnet.net
- Subject: [mg45743] Re: Tail recursion and local functions
- From: Matthew McDonnell <kebl1405 at herald.ox.ac.uk>
- Date: Fri, 23 Jan 2004 03:15:26 -0500 (EST)
- Organization: Oxford University, England
- References: <buiv4p$qtn$1@smc.vnet.net> <bulof0$8hb$1@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
Paul Abbott <paul at physics.uwa.edu.au> wrote:
> 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.
Hi Paul,
My initial thought was that tail recursion is commonly used in
functional programming languages to speed up functions and reduce stack
usage, so it seemed an interesting exercise to translate it to a standard
example Mathematica function i.e. factorial. Probably not overly useful
unless I get involved with recursive data structures.
<snipped to avoiding recursion and iteration limits>
> $RecursionLimit = Infinity;
>
> $IterationLimit = Infinity
This is useful to know, thanks!
<snipped>
> 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]]
>
No, there was a typo but that wasn't it - I meant to write
aux=Function[{i,acc},If[i<=0, acc , aux[i-1,i acc]]];
^^^
i.e. each call to aux holds the current value of the factorial being
calculated so that when it hits the base case of the recursion it exits
rather than recursing back upwards again.
As Hartmut points out further downthread, the problem with this was trying
to declare and initialise the local function in one step - in the
recursive step it then tries to access the (non-existant) global function
aux. Correct syntax would be ...Module[{aux}, aux=...; aux[n,1]]...
> Cheers (from your alma mata),
> Paul
Glad you still remember me! :)
Hopefully not too long before I'm back for a visit - came back last July,
probably back again at the end of this year.
Cheers,
Matt