A CS professor once explained recursion as follows:
A
child couldn't sleep, so her mother told her a story about
a little frog,
who couldn't sleep, so the frog's mother told her a story about
a little bear,
who couldn't sleep, so the bear's mother told her a story about a little weasel...
who fell asleep.
...and the
little bear fell asleep;
...and the
little frog fell asleep;
...and the
child fell asleep.
This is the best explanation of recursion I've heard. It could probably be recast to be less cutesy, but it really gets to what's
going on with recursion in a very nice way: Stuff happens on the way in, you hit an
endpoint, and other stuff happens in reverse order on the way back out as it all
unwinds. For somebody who doesn't "get" recursion yet, this is not a bad map to start with.