The question really is, can you code it recursively without paying severe performance penalty? (Why else would you avoid recursion if a recursive solution is shorter, simpler, more robust, etc.)
Answer: yes. fib=: 3 : 0 M. if. 2>y do. y else. (fib y-1) + (fib y-2) end. ) fib1=: 3 : 0 if. 2>y do. y else. (fib1 y-1) + (fib1 y-2) end. ) 6!:2 'fib 25' 0.000897321 6!:2 'fib1 25' 1.52873 See http://www.jsoftware.com/jwiki/Essays/Fibonacci_Sequence Another example is found in the M. dictionary page and the for. page. http://www.jsoftware.com/help/dictionary/dmcapdot.htm http://www.jsoftware.com/help/dictionary/cfor.htm comb=: 4 : 0 M. if. (x>:y)+.0=x do. i.(x<:y),x else. (0,.x comb&.<: y),1+x comb y-1 end. ) comb1=: 4 : 0 if. (x>:y)+.0=x do. i.(x<:y),x else. (0,.x comb1&.<: y),1+x comb1 y-1 end. ) comb2=: 4 : 0 k=. i.>:d=.y-x z=. (d$<i.0 0),<i.1 0 for. i.x do. z=. k ,.&.> ,&.>/\. >:&.> z end. ; z ) 6!:2 '10 comb 20' NB. double recursion with M. 0.170501 6!:2 '10 comb1 20' NB. double recursion without M. 4.38387 6!:2 '10 comb2 20' NB. iterative 0.118327 comb and comb1 are easier to understand and have been known since the 1960s (in Gilman & Rose); comb2 has been worked on for about 30 years. Yet the simple recursive defn, with an assist from M., is within a factor of 2 of the highly worked over version. ----- Original Message ----- From: gary ng <[email protected]> Date: Thursday, May 14, 2009 11:38 Subject: Re: [Jprogramming] tail recursion/TCO? To: Programming forum <[email protected]> > On Thu, May 14, 2009 at 11:20 AM, Raul Miller > <[email protected]> wrote: > > > > So if by 'serious' you mean coding in 'pure' style(i.e. no > fallback to > > > loop), I am curious to know how can one implement algorithms > that needs > > > recursion in J. > > > > For example: > > 1 2 3 + 4 > > 5 6 7 > > > This is an example that no recursion is needed. The text book > example would > be fibonacci number. Even in language like F# which has TCO, it > needs to be > twisted a bit to make it 'TCOtable'. Haskell solution is elegant > and simple > due to its laziness not that it has TCO. > > How would that be implemented in J without recursion and while > loop ? ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
