I stand corrected :)


"Warp" <war### [at] tagpovrayorg> wrote in message
news:411e9bc0@news.povray.org...
> 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