[racket] recursion??

On Jun 5, 2012, at 7:37 AM, Ronald Reynolds wrote:

> I hope I'm not too much of a 'pain in the neck noobie' but what is the short clean answer about what's going on when we
> name a function as part of the definition of itself..  This seems pretty esoteric to me.  What does the system do?  

By "what's going on", are you talking about how it's implemented inside the computer, or how people use this technique to solve problems?

For the former, you would need to know something about memory organization, machine or assembly language, stacks, etc.

For the latter, let's try this analogy.  I'm a custodian, assigned to clean each of the rooms on a long hallway.  But I'm lazy, so after cleaning one room I tell my assistant to clean the rest.  My assistant is lazy too, so after cleaning one room he tells HIS assistant to clean the rest.  That second assistant is equally lazy, so after cleaning one room she tells HER assistant to clean the rest.  And so on down the hallway.  Eventually my 27th sub-assistant is assigned to clean "the rest of the rooms", but realizes that he's already at the end of the hallway, so he can report that he's finished without cleaning anything at all.  His boss reports having accomplished the task she was assigned, as does her boss, and his boss, and his boss, and so on, until word gets back to me that my assistant has accomplished what I told him to do, at which point I announce that I, too, have accomplished what I was told to do.

Now suppose all of these custodians are not just equally lazy, but are actually clones of one another, or are a bunch of identical robots, or something like that.  Every one of them follows the exact same rule: "If there are rooms left to clean, clean one of them and tell my assistant to do the rest.  If not, declare success and go home."  Since they all follow the same rule, it only needs to be written once.
Another name for "rule" is "program" or "function"; you can think of the computer as creating a whole bunch of assistants, each one giving the next one an assignment and waiting for him/her to finish.

Now, what would happen if the custodians were even lazier?  When I'm assigned to clean all the rooms on this hallway, I IMMEDIATELY tell my assistant to do the job (the WHOLE job, not "the rest").  My assistant, being equally lazy, immediately tells his assistant to do the job, and so on: soon an infinite number of assistants are telling one another what to do, with nobody ever actually picking up a broom.  This is the most common mistake people make in writing recursive programs: they call the same function to solve THE SAME PROBLEM rather than to solve A SMALLER PROBLEM.

It could be even worse: suppose, after being assigned to clean all the rooms on the hallway, I pick a clean room and hold a drunken party in it, then assign my assistant to clean this room as well as all the rooms I was assigned.  My assistant does the same, and rather than having fewer and fewer rooms left to clean, we have more and more.  In other words, the function calls itself to solve A LARGER PROBLEM than it itself was given.


Stephen Bloch
sbloch at adelphi.edu

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20120605/877f4e37/attachment.html>