When I was a little kid, there was a toy that I desperately wanted. We'll just gloss over what it was because it's not in any way important to the story. So one night --
All right, all right, stop whining. I'll tell you. It was... a Ronald McDonald doll. That whistled. Yes, it had a little plastic whistle, and if you squeezed it then it would whistle. As seen on TV. Why in the world would I want that? I have no idea. I just remember that it seemed very important at the time.
So I wanted this Ronald McDonald doll. Very much. But I knew that my dad, who has always been a practical minded guy, would find this toy, well, stupid. So I didn't have the courage to ask him for it. But then to my surprise, one evening I came home from school, and my dad said, "Russell, today we're going to Toys R Us to pick up that Ronald McDonald you've been wanting."
Needless to say, I was ecstatic. We got in the car, drove to the store at the mall, picked up that toy, brought it home, and...
...Then I woke up.
As bitterly disappointed as I was to learn that it was all just a dream, I was filled with a new confidence. I just knew that my dad was going to buy that toy for me, because the dream had so foretold. So I went into the breakfast nook, where I found my dad waiting. I asked him if he would get me the Ronald McDonald doll that whistles, and he says "Surprise! I already got it for you! There it is!"
...And I woke up.
But after having been through this experience twice, I was more certain than ever that I would be getting my toy. Sure enough, I went to find my dad, asking "Did you REALLY get me that toy?" He said "I sure did! Look!" I actually got to play with the thing for a while, and then -- all together now,
...I woke up.
I think you get the idea. It feels like the sequence repeated itself about ten times or so, although of course there's no way to tell. Each time the details of the nested dream were a little different, but the end result was always the same: I was confident that I'd get the toy, I did get the toy, and I woke up. And each time I woke up, the world seemed a little more "real" to me than the one in the previous dream.
Except for the last time. When I really woke up, I knew I was really awake. I didn't even need to bother asking my dad about it in the real world. I know reality.
I never did get that toy. That probably explains exactly why I am the bitter cynic I am today.
The tricky part about this story is still how to translate it from amusing anecdote to actual concept of computer science. If this were true recursion, I would probably remember going to sleep ten times in a row at the beginning, then getting the toy for the first time, and so on. Instead, I started in mid-dream. But nobody ever remembers going to sleep anyway, so we can assume that happened in there somewhere. So if I had to pseudo-code this story, it would look like this:
class YoungRussell {
void sleep () {
lieDown(bed);
fallAsleep();
dream();
// perform operations associated with
// waking up here
}
void dream () {
if(someTerminatingCondition() == false) {
// no actions before falling asleep
// again in the dream
sleep();
}
StupidToy ronald = new StupidToy();
obtain(ronald);
playWith(ronald);
}
// ...
// auxiliary methods here
}I have always found this the hardest thing for people to understand about recursion.
A couple quick thoughts about recursion:
ReplyDelete- the most famous programming application of recursion is probably the Towers of Hanoi problem:
http://en.wikipedia.org/wiki/Tower_of_Hanoi
you guys with formal programming education are certainly familiar with this. I'm self-trained in CS and ran across this once studying for a job interview. I've tried, and failed, to apply recursion to certain problems I've encountered since in my jobs. There's not a huge class of problems that are amenable to recursive solutions ;).
- recursive solutions have crucial non-recursive aspects to them. They require a "base case" that has to be tested each time through in order to terminate. And some aspect of the routine has to change each time through in order to reach the base case.
I.e. this function that computes the sum of all ints from 1 to n that I found on the internet:
int sum(int n) {
// post: return the sum of ints from 1 to the given value
if (n < 1)
return 0;
else
return sum(n - 1) + n;
}
This is the hardest thing to grasp about recursive solutions for me. Self-reference is a simple concept, i.e.
int sum(int n)
{
return (sum (n-1)+n);
}
but insuring that there's a base case and that each recursive call can eventually reach it is the real meat of the recursive solution.
- a formal definition of a situation like that comes from from formal language theory, known as left recursion:
http://en.wikipedia.org/wiki/Left_recursion
You compiler writers out there are familiar with this one. Your grammars have to be purged of left-recursive rules before you start writing your parsing code. fortunately, there's an algorithm to do this for context-free grammars.
LS
Oh, one other kind of nuts-and-bolts thing about recursion occurred to me while I was cooking breakfast. I hope this analysis is right, er, I think it is, but correct me if it's not.
ReplyDeleteOne drawback of recursive solutions is they eliminate some opportunities for optimization. For example, on the X86 CPU's, you can't take advantage of the different calling conventions available in most compilers to optimize function calls in the way you could with non-recursive situations.
For example, the "cdecl" calling convention - where, IIRC, the calling function does the stack cleanup - can result in smaller code for functions that get called a bazillion times (you don't have to generated the stack cleanup code a billion times, just once at the call site and that's it). This optimization is available in a non-recursive solution where the caller and callee are different functions:
extern void __cdecl foo(int a);
void bar()
{
for (int i=0....)
{
foo(i);
.....
}
But note that in a recursive solution, where the caller and callee are the same function, this optimization isn't really available. The function is both caller and callee in the routine, so it doesn't really matter for purposes of optimization who is designated to do the stack cleanup.
That's one reason I've heard that non-recursive solutions should be exhausted first, at least in compiled languages like C/C++, before a resort is made to recursive ones.
Just something I remember from way back...
LS
LS,
ReplyDeleteI wrote my own Towers of Hanoi applet. Here it is. For some reason I don't understand, the applet is blocked for me when I view it at work, but I'm not sure if it's my web server or my filter at work causing the problem. I hope you can see it, because I made some pretty fancy graphics for it and it's cool looking.
Anyway, in a previous incarnation of this program (visual C++) I had a "Genie" who would solve the puzzle for you. I never got around to coding it in this version, but the first thing I had to do when writing it was to remove the recursion by turning it into a iterative implementation. I wanted the Genie to be able to give "hints" by solving for one move at a time, so I couldn't have it run an entire recursive solution.
Implementing recursive solutions has very limited use, because it is not thread-friendly unless the depth is fairly limited or the individual steps are very quick (i.e., you can't do any kind of animation recursively). However, it is valuable to understand how recursion WORKS, so that you can think of a recursive solution first and then implement your own stack-based solution that can perform one step at a time.
your lucky the last time I had a recursive dream it was because there was something I had to do in the morning that I was not looking forward to, and I found myself repeatedly waking up to realize that all the stuff I had done that morning was just a dream.
ReplyDelete