Tail recursion and local functions



  • 1. Cuda offline installation in M8
    Hi, i tried to install Cuda offline by the method described in Mathematica help. Needs["CUDALink`"] CUDAResorucesInstall["<path_to_paclet>"] but nothing happened. i wondered that this problem might be related to my hardware because in Geforce supported list "gtx 470" not found or anything else. thanks
  • 2. Help Browser CPU Usage
    Hi All, I am using Mathematica 7.0 on a dual processor Linux system and am seeing that if I bring up the Function Navigator - Add Ons & Packages - Add Ons and then select the Help for AddOn packages from version 5.2 (a bunch of nb under the Documentation/English directory) the cpu usage increases to unacceptable values - Mathematica usage from about 10% to 20% and xorg usage from a few % to over 80%. Currently I just open and then close the help browser which is inconvenient. I would like to keep it open as I work. Is this "normal" or is it something I can fix? Is Mathematica doing something in the background as I use these for the first time and should I just be patient and it will finally finish up? Do I need to do something to "rebuild" the legacy help for Version 7.0? Thanks for any help. Ron Burns -- R. R. Burns Physicist (Retired) Oceanside, CA
  • 3. Function Equivalence of ArcTan and Log
    Hi, I have a problem to show with Mathematica (using already TrigToExp and ComplexExpand) that In[1]:= s1=(ArcTan[x-I y]-ArcTan[x+I y])//TrigToExp Out[1]:= 1/2 I Log[1-I (x-I y)]-1/2 I Log[1+I (x-I y)]-1/2 I Log[1-I (x+I y)]+1/2 I Log[1+I (x+I y)] and In[2]:= s2=I/2 Log[(x^2+(1-y)^2)/(x^2+(1+y)^2)]//ComplexExpand Out[2]:= I (1/2 Log[x^2+(1-y)^2]-1/2 Log[x^2+(1+y)^2]) are identical, i.e. s1===s2 should give "True". But FullSimplify applied to lhs or rhs does not help. Of course, the identity wanted can be derived by hand making use of the inverse function Tan[s1]==I z and Sin[s1], Cos[s1] etc. which gives rise to the following replacement rule : ArcTanToLog = {(ArcTan[x_-I y_]-ArcTan[x_+I y_])-> I/2 Log[(x^2+(1-y)^2)/(x^2+(1+y)^2)]} It is, however, non-trivial to prove this identity purely with term rewriting by means of Mathematica. Any suggestion is appreciated. Thanks in advance, Robert Kragler

Tail recursion and local functions

Postby Matthew McDonnell » Wed, 21 Jan 2004 19:15:53 GMT

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 

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?


Re: Tail recursion and local functions

Postby Jens-Peer Kuska » Thu, 22 Jan 2004 20:24:50 GMT


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

work a expected.


RE: Tail recursion and local functions

Postby Wolf, Hartmut » Thu, 22 Jan 2004 20:28:58 GMT

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

Re: Tail recursion and local functions

Postby Paul Abbott » Thu, 22 Jan 2004 20:40:16 GMT

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

Re: Tail recursion and local functions

Postby Matthew McDonnell » Sat, 24 Jan 2004 17:30:22 GMT

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!


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.


Return to Mathematica


Who is online

Users browsing this forum: No registered users and 30 guest