Subj : Re: Are recursive functions ever needed?
To   : comp.programming
From : robertwessel2@yahoo.com
Date : Mon Oct 03 2005 09:45 pm


Simo Melenius wrote:
> Tatu Portin <axel86@mbnet.fi> writes:
>
> > Well, my problem here seems to be lack of good examples where
> > recursion is needed. Would anybody provide some?
>
> Well, think of quicksort.
>
> As others have pointed out, you can generally simulate the effect of
> recursion with a loop plus a stack. And that it's often a choice about
> which-fits-best.
>
> But as an example, quicksort the algorithm is inherently of recursive
> nature. It applies itself again to finish its own job -- that's just
> the way it works. When programming quicksort it's definitely best
> expressed as a self-recursive function, because that better reflects
> its nature.
>
> The reader should feel free to try to implement an iterative quicksort
> that's somehow "more iterative" than a straight-forward translation
> into a loop that uses a stack/list to keep track of the boundary
> indexes/nodes. That should help in seeing something, I hope.


While it's easy and obvious to express Quicksort in a fully recursive
form (where both partitions are sorted recursively), the result is,
unfortunately, unusable in the real world since you have potentially
unbounded (OK, proportional to N) stack usage.

A partially recursive implementation, where the smaller partition is
sorted with a recursive call and the larger one with an iteration, is a
popular solution that avoids the complexity of an explicitly managed
stack as well as the explosive stack growth problem.

.