Combinations and recursion, from an ASPN snippet

[Greg Ewing (using news.cis.dfn.de)]

Andy Jewell wrote:
> I like to think of recursion as 'nesting' calls to the function, one inside 
> the other:
> 
> 1
>   \
>     2
>       \
>         3
>           \
>            4
>              \
>               :
>              /
>            4
>           /
>         3
>       /
>     2
>    /
> 1
> 
> Bear in mind, though, that it won't usually be as 'tidy' as this!

Indeed. If your call graph is just a straight line down to the bottom
and back up, you're probably better off using a loop -- it'll be
faster, use much less stack space, and probably be just as clear.

Recursion really comes into its own when the call graph is some
sort of tree structure. Then you get n recursive calls for only
log(n) worth of stack space, and the use of recursion can
tremendously simplify the program logic, since you're really
making use of the stack-ness of the stack.

-- 
Greg Ewing, Computer Science Dept,
University of Canterbury,	
Christchurch, New Zealand
http://www.cosc.canterbury.ac.nz/~greg