Doppelganger <ped### [at] netcabopt> wrote:
> unless there's a serious bug involved they're always the
> same order

  Same order, of course, but the constant factor is bigger for recursive
programs, which means that it will be slower than the iterative one.

> "While it's proven that certain algorithms can only be done recursively"

> Quicksort is a case, if I'm not mistaken. In fact I think it's thought of as
> massively recursive, whatever that means

  In the case of quicksort you know how deep your iteration stack will
at maximum be before you start sorting. This means that you can allocate
a properly sized stack (which size keeps fixed during the whole execution
of the algorithm) and use it to make an implementation without recursive
function calls.
  Since the stack can be allocated at the beginning and its size doesn't
need to be modified during the algorithm, and since the algorithm can
then be implemented without using recursive function calls (just using
this stack to "emulate" recursiveness), its speed should be possible
to be made equivalent to an iterative algorithm.

  In this regard quicksort is not one of the worst algorithms if
recursion is a big problem. There are, however, algorithms where
there's no way to predict how deep the recursion stack will be,
and those are more problematic.

-- 
plane{-x+y,-1pigment{bozo color_map{[0rgb x][1rgb x+y]}turbulence 1}}
sphere{0,2pigment{rgbt 1}interior{media{emission 1density{spherical
density_map{[0rgb 0][.5rgb<1,.5>][1rgb 1]}turbulence.9}}}scale
<1,1,3>hollow}text{ttf"timrom""Warp".1,0translate<-1,-.1,2>}//  - Warp -

Post a reply to this message