gary ng-2 wrote: > > 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. > Funny you should mention that Python does not support tail-recursive optimization since sbcl's compiler, Python, does support it, directly in assembly.
Here is the snippet of the Python-produced code for the tail-recursive definition of factorial: --------------------------------------------------------------- $ sbcl This is SBCL 1.0.18.debian, an implementation of ANSI Common Lisp. [...skipping few lines...] * (defun fac(n)(if(zerop n)1(* n(fac(1- n))))) FAC * (disassemble 'fac) [...skipping 12 lines...] ; 93: 488BDC MOV RBX, RSP ; 96: 4883EC18 SUB RSP, 24 ; 9A: 488B055FFFFFFF MOV RAX, [RIP-161] ; #<FDEFINITION object for FAC> ; A1: B908000000 MOV ECX, 8 ; A6: 48896BF8 MOV [RBX-8], RBP ; AA: 488BEB MOV RBP, RBX ; AD: FF5009 CALL QWORD PTR [RAX+9] ; B0: 480F42E3 CMOVB RSP, RBX ; B4: 488BFA MOV RDI, RDX ; B7: 488B55E8 MOV RDX, [RBP-24] ; BB: 4C8D1C25C9020020 LEA R11, [#x200002C9] ; GENERIC-* ; C3: 41FFD3 CALL R11 ; C6: 480F42E3 CMOVB RSP, RBX ; CA: L0: 488D65F0 LEA RSP, [RBP-16] ; CE: F8 CLC ; CF: 488B6DF8 MOV RBP, [RBP-8] ; D3: C20800 RET 8 [...9 lines left... the above comments are produced by Python.] --------------------------------------------------------------- The recursive call remains, but the stack pointer is "rewound" so that the current value of n is not saved but overwritten, so no growth of stack takes place. All of this is very fast: --------------------------------------------------------------- 0[2] (time(fac 1000)) Evaluation took: 0.001 seconds of real time 0.000000 seconds of total run time (0.000000 user, 0.000000 system) 0.00% CPU 1,308,349 processor cycles ... 4023872600770937735437024339230[...gives all digits...] 0[2] (defun fact(n)(let((f 1))(loop for i from 2 to 1000 do (setq f(* i f)))f)) [...warnings...] FACT 0[2] (time(fact 1000)) Evaluation took: 0.001 seconds of real time 0.000000 seconds of total run time (0.000000 user, 0.000000 system) 0.00% CPU 1,156,211 processor cycles ... 4023872600770937735437024339230[...gives all digits...] --------------------------------------------------------------- To be fair it should be also mentioned that clisp supports optimized compilation of tail-recursive functions. It is most instructive to try (disassemble 'fac) in clisp as well, as it will give much shorter annotated byte-code listing of the compiled code. Optimized tail-recursion is fairly straightforward to implement and it is worth the effort if one cares about recursive programming. -- View this message in context: http://www.nabble.com/tail-recursion-TCO--tp23530610s24193p23566778.html Sent from the J Programming mailing list archive at Nabble.com. ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
