[Tutor] Re: Recursion....what are the best situations to use it?

[Kent Johnson]

jsoares at Safe-mail.net wrote:
> I've seen a couple of nice tutorials on recursion, and a lot of awful 
> ones. The latter always trot out the fibonacci and factorial examples 
> for some reason. And that's about it! The good ones showed me how to 
> trace through recursive calls and gave me practical examples(tictactoe, 
> magic squares, Tower of Hanoi, 4-Square, etc)
> 
> What I want to know is this: what are other specific situations where a 
> recursive algorithm would be better or easier to program than an 
> iterative one?

Many algorithms that break down into sub-parts that have the same structure as the main algorithm 
can naturally be expressed recursively.

For example flattening a list that may contain sublists can be expressed something like this:
def flatten(l):
   result = []
   for item in l:
     if type(item) == list:  # (This test is a bit simplistic)
       result.extend(flatten(item))
     else:
       result.append(item)

Another good candidate for recursive processing is tree algorithms, for example printing out nodes 
of a tree.

I once wrote an audit engine for a dom tree that recursively descends the dom tree and a tree of 
audit rules at the same time. I wrote about it here:
http://www.pycs.net/users/0000323/stories/2.html

There are non-recursive ways of doing these things also. But IMO the recursive formulation is often 
easier to understand.

Kent