From: Robert Klemme Date: 2003-08-07T18:45:17+09:00 Subject: Re: Ruby Query "Gavin Sinclair" schrieb im Newsbeitrag news:36655.203.185.214.34.1060244308.squirrel@webmail.imagineis.com... > I am out of my depth here, but calculating factorial recursively is not > intrinsically inefficient, as it can be defined in a tail-recursive manner > (unlike fibonacci). It's Ruby that's inefficient by not "supporting" > tail-recursion optimisation, not the algorithm itself. Hmmm, I don't fully agree to you. Maybe nowadays one expects such optimizations from a compiler / execution environment because they are quite common. Nevertheless a method call (unless optimized away) imposes a performance hit and thus defining a function recursively tends to be slower. The algorithm per se (i.e. effort measured as O calculus) does not differ since the number of executions (either loopings or by recursions) stays the same. So I'd like to refine your statement to "a recursive algorithm is not intrinsically inefficient". But an implementation has to consider the environment (language, compiler, runtime) and I'd claim that on average a recursive algorithm that can be transformed into an iteration tends to be slower. > That said, your > benchmarks (snipped) show a speed difference of only a factor of two > between iterative and recursive, which surprised me. > > Further proof that Ruby does not truly have POLS! What did you expect? 100? :-) Regards robert