On Thu, May 14, 2009 at 12:48 PM, Roger Hui <[email protected]> wrote:
> 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 > Memoization helps though the question would be what happens if I say 'fib 10000' or whatever number that exceed the recursion limit. Python has this limit though Guido has expressed that he is of no interest in implementing TCO. So naturally, I tend not to code in this style but use the 'generator' idiom and Memoization still benefits. ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
