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
_______________________________________________ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
