[ruby-talk:03666] Re: Another small quiz

> When I watched fact with bigger arguments, the recursion gets slower and 
> slower, so I wonder if recursion is fine in interpretative environment.

It is usually assumed that an addition is O(1) time and a multiplication
is O(1) time as well. When working with very large integers (much greater
than +/- 2^30) it becomes false.

a + b takes log(a + b) time.

a * b takes log(a * b) time.

factorial of n takes sum(1..n,{|x| log(fact(x)) }) time.

log(fact(x)) is about x*log(x)  (???)

a sum of x*log(x) over x in 1..n takes about n**2 * log(n) if i'm
not mistaken. (???) at least it's between n**2 and n**3.

anyway, regardless of the actual result, i think you get the picture, and
we are pretty far away from straight linear time; what language you
implement it in is irrelevant.


> I cannot recall who advised to replace recursion with iteration wherever 
> possible; even though it is claimed that recursion is natural but 
> complicated recursion is not easy to grasp.

complicated recursion is difficult to grasp because it's complicated, not
because it's recursion. same goes for complicated iteration. 

also, "easy to grasp" is relative. It's not easy when there's a
significantly easier way of doing it; it is when there is not.



Mathieu Bouchard