> Is this the reason why I read on wikipedia(may be some where > else) that this is not solvable in J ?
No, the problem with Ackermann's function is not so much the call stack but that the function value grows extremely quickly, and you'd have problems representing the result in any general programming language. x ack y is limited to x<:5 for all practical purposes, and for such x and y: 0&ack = >:&.(3&+) NB. >: 1&ack = 2&+&.(3&+) NB. 2&+ 2&ack = 2&*&.(3&+) NB. 3&+@(2&*) 3&ack = 2&^&.(3&+) 4&ack = ^/@(#&2)&.(3&+) 5&ack = 3 : '^/@(#&2)^:(1+y)&.(3&+) 1' http://www.jsoftware.com/jwiki/Essays/Ackermann's_Function ----- Original Message ----- From: gary ng <[email protected]> Date: Thursday, May 14, 2009 12:44 Subject: Re: [Jprogramming] tail recursion/TCO? To: Programming forum <[email protected]> > On Thu, May 14, 2009 at 12:07 PM, Devon McCormick > <[email protected]>wrote: > > Fibonacci is a bad example because it has a closed-form > solution. In J: > > > > *fibonacci*=: 3 : 0"0 > > b=. - a=: % sqrt5=. %: 5 > > (a * (-:1+sqrt5) ^ y) + b * (-:1-sqrt5) ^ y > > ) > > > > When I used this as an example, I was meant to say how to solve > it in a > 'loop' manner not the closed form solution as most language > would take that > route as a demonstration of how that kind of problem would be tackled. > > > > Ackermann's function is a better example but this is coded in > a recursive > > manner on the J wiki: > > > > ack=: c1`c1`c2`c3 @. (#.@(,&*)) > > c1=: > >:@] NB. if 0=x, 1+y > > c2=: <:@[ ack > 1: NB. if 0=y, (x-1) ack 1 > > c3=: <:@[ ack [ ack > <:@] NB. > else, (x-1) ack x ack y-1 > > > > (from http://www.jsoftware.com/jwiki/Essays/Ackermann's Function). > > > So woul this boom when it exceed the recursion limit of J ? > > > > > > > > I also would be interested in seeing this done without > recursion as it > > looks > > to be so fundamentally recursive that it may be impossible to > do it > > otherwise. > > > > Is this the reason why I read on wikipedia(may be some where > else) that this > is not solvable in J ? ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
