[Tutor] Re: Recursion....what are the best situations to use it?
Kent Johnson
kent37 at tds.net
Fri Apr 15 00:23:54 CEST 2005
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
More information about the Tutor
mailing list