Mathematica 9 is now available
Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2004
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2004

[Date Index] [Thread Index] [Author Index]

Search the Archive

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


  • Prev by Date: RE: Re: Anyone using the Units package extensively?
  • Next by Date: RE: Tail recursion and local functions
  • Previous by thread: Re: Tail recursion and local functions
  • Next by thread: RE: Tail recursion and local functions