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

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


  • Prev by Date: Package dependencies
  • Next by Date: Re: Inappropriate Domain Calculation Warnings
  • Previous by thread: Re: Package dependencies
  • Next by thread: Re: Tail recursion and local functions