> 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?
Hello,
Programs that have to deal with data often have an internal structure that
mimics that data. A program that deals with lists looks slightly
different from one that doesn't deal with lists. And if the data that we
deal with is recursive, then we may want our program to have a recursive
structure too. So recursive algorithms work best on recursive data.
This is a bit circular, so let's sketch a quick example to make this
concrete.
If we were to write a program to grab all the names in a directory of
files, we have a situation where the thing that we're processing has an
internal structure that itself can contain substructures. Your computer's
file system has a recursive shape!
When use use a general term "file", we really mean one of the following:
1. a directory
2. a regular, non-directory file
And we know that a directory is itself a list of files. Slightly more
formally, we can use a few funny symbols and say that:
file ::= directory | regularfile
directory ::= list of file
"A file is made up of either a directory or a regular file"
"A directory is made up of a list of files"
It's a little loopy if you think about it, which is exactly why programs
that deal with directories are often recursive.
If we wanted to get a list of all the regular files in a particular
directory, then it's natural for our program's structure to mimic this
recursive structure. We might say:
### Pseudocode ###
def listAllRegularFilesInDirectory(someDirectory):
## ... fill me in. We'll probably have to refer to
## listAllRegularFilesInFile() somewhere in here.
def listAllRegularFilesInFile(someFile):
if someFile is a directory:
return listAllRegularFilesInDirectory(someFile)
else if someFile is a regular file:
return listAllRegularFilesInRegularFile(someFile)
def listAllRegularFilesInRegularFile(someRegularFile):
## ... fill me in. This one is easy: just return a list with a single
# element.
######
This is a quick sketch of a recursive program to get at all the regular
files, and its form is strongly influenced by the data structure that it
works with.
Once we have the recursive version working, we can optimize it to remove
the explicit recursion by using a stack. But the fundamental algorithm
for going through the directories is recursive traversal.
Does this make sense? There are actually a lot of data out there that
have recursive structure. One of the the most visible being web pages,
since web pages have links to other web pages.
So recursion is very fundamental: master it, and certain programs get a
lot easier to solve. But I have no clue why factorial() seems to be the
main doorway to recursion. *grin*
Most Lisp or Scheme books will use recursive ideas as a major focus, so if
you really want to learn more, you might want to look at a book like "How
To Design Programs":
http://www.htdp.org/
or the Little Schemer.
Best of wishes!
_______________________________________________
Tutor maillist - Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor
