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

Re: Re: Re: Mathematica:recursion with 2 arguments?

• To: mathgroup at smc.vnet.net
• Subject: [mg64715] Re: [mg64711] Re: [mg64426] Re: Mathematica:recursion with 2 arguments?
• From: Murray Eisenberg <murray at math.umass.edu>
• Date: Wed, 1 Mar 2006 04:11:35 -0500 (EST)
• Organization: Mathematics & Statistics, Univ. of Mass./Amherst
• References: <dspfp8$cfh$1@smc.vnet.net> <200602170911.EAA00666@smc.vnet.net> <200602281002.FAA22215@smc.vnet.net>
• Reply-to: murray at math.umass.edu
• Sender: owner-wri-mathgroup at wolfram.com

This function, known as Ackermann's function, is a classic example of a 
recursive function that is not primitively recursive.

Programming and computing this function is often an exercise foisted 
upon innocent students by computer science professors.  As you 
discovered, the stack involved in computing the function grows very 
rapidly, even for small inputs.  It's the nature of the beast!


leigh pascoe wrote:
> OT wrote:
> Hi,everybody:
> My English is a little poor.But I have a very flustered problem to consult you.Who can help me? Here is the prob:
> IF function f(m,n)(m,n are non-negative integers)satisfying 3 conditions: f(0,n)=n+1,f(m+1,0)=f(m,1) and f(m+1,n+1)=f[m,f(m+1,n)],then how can we use Wolfram's Mathematica to solve f(m,1),f(m,2),f(m,3) and so on.I can get f(1,n)=n+2,f(2,n)=n+3,f(3,n)=2^(n+3)-3 by hand and pen(but how by Mathematica?).Surely,f(4,n) is very complicated.
> Who can use Mathematica's language (recursion or iteration etc.) to solve them out? Friends,help me--a poor person,please!!!!!!
> 
> ClearAll[g]
> g[m_, 0] := (g[m, 0] = g[m - 1, 1]) /; (m > 0)
> g[m_, n_] := (g[m, n] = g[m - 1, g[m, n - 1]]) /; m*n > 0
> g[0, n_] := n + 1
> g[0, 0] = 1
> 
> 
> this works, but if you try to calculate it for m >= 4 you will get the 
> error "$RecursionLimit::reclim: Recursion depth of 256 exceeded."
> 
> You can try to find more rules to "simplify some recursions", or put 
> $RecursionLimit = Infinity and wait some hours...
> 
> 
> A simple function that will generate all the values quickly is
> 
> f[m_,n_]:=m+n+1
> 
> This function satisfies the three initial recurrence relations and
> doesn't rely on recursion to generate values. 
> 
> LP
> 
> 

-- 
Murray Eisenberg                     murray at math.umass.edu
Mathematics & Statistics Dept.
Lederle Graduate Research Tower      phone 413 549-1020 (H)
University of Massachusetts                413 545-2859 (W)
710 North Pleasant Street            fax   413 545-1801
Amherst, MA 01003-9305