Tail recursion and local functions

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

Hi,

fact3[n_:Integer] := 
  Module[{aux}, aux = Function[{i, acc}, If[i <= 0, acc, aux[i - 1, i
acc]]]; 
    aux[n, 1]]

work a expected.

Regards
  Jens

No, Matt, apart from the obvious typo, this doesn't work (as perhaps
suspected from the result: where does global variable aux come from?)
Recognizing something peculiar, Module/Function scoping rename aux from
Module to aux$ (not to aux$56 e.g.) but at this place (declaration of local
aux) aux from the body of the function refers to global aux.

You can avoid this delaying the definition:

In[33]:= fact3X[n_:Integer] := 
  Module[{aux}, aux = Function[{i, acc}, If[i <= 0, acc, aux[i - 1, i
acc]]]; 
    aux[n, 1]]

In[34]:= fact3X[10]
Out[34]= 3628800


It works however for Block (and this should not surprise):

In[29]:= fact3B[n_:Integer] := 
  Block[{aux = Function[{i, acc}, If[i <= 0, acc, aux[i - 1, i acc]]]}, 
    aux[n, 1]]

In[30]:= fact3B[10]
Out[30]= 3628800



Perhaps you are interested in this pure function construct:
 
In[42]:= fact3P[n_Integer] := If[#1 <= 1, #2, #0[#1 - 1, #1 #2]] &[n, 1]

In[43]:= fact3P[10]
Out[43]= 3628800


All these are $IterationLimit-ed.

In article <buiv4p$qtn$ XXXX@XXXXX.COM >,




Not sure why you really want or need these in Mathematica.


Mathematica allows local functions to be defined within functions.


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]] &;


Similarly, you can get around this by setting 

  $IterationLimit = Infinity


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]]
 

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: XXXX@XXXXX.COM  
AUSTRALIA                             http://www.**--****.com/ ~paul

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>
This is useful to know, thanks!

<snipped>

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]]...


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