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