[racket] recursion??

[Ronald Reynolds]

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?  

[Rüdiger Asche]

I'm not sure what you mean by "when we name a function as part of the
definition of itself," but since the title of your question is
"recursion," I'll just answer as if you had asked "when we write a
function that recursively calls itself," hoping that that's what you
meant...

Best place would be to study the documentation for letrec:

"Similar to let, but the locations for all ids are created first and
filled with #<undefined>, and all ids are bound in all val-exprs as
well as the bodys. "

I believe this pretty much explains it? It's mostly about scoping and
name spaces which are really fundamental concepts within Scheme, so
it's worth looking into those concepts a little bit more in depth.

In the case of #define, the global name space is used which the body
of the function can always access.



____________________
Racket Users list:
http://lists.racket-lang.org/users

[Stephen Bloch]

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

sbl...@adelphi.edu

[Ravi Chemudugunta]

On Tue, Jun 5, 2012 at 11:37 PM, Ronald Reynolds <bum...@bumpker.com> 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?  

If "by name a function as part of the definition of itself" you mean, the body of a function contains a call to the function that is being defined:

Short answer is, there is nothing special going on - except that define is a special form but define being a special form does not have anything to do being able to recursively call functions. I recommend reading up on metacircular evaluator, (see SICP) - and going through the code by hand/pen/paper.

--
C-x C-s, C-x C-c

[Marco Morazan]

I am not sure what you mean by esoteric. The simple answer is that you
are applying a function to some input. It just happens to be that the
function being called is the same function that is being evaluated.
The longer answer is that the function is being evaluated in an
environment that contains a definition for itself. Thus, it can call
itself. Others have suggested pointers into the literature for the
finer details of implementation.

Hope it helps,

Marco



--

Cheers,

Marco

[Ronald Reynolds]

Is it correct to say that when I call a function inside of it's own definition I am just making it repeat loop?  

(define (my-map f lst)   (cond    [(empty? lst) empty]    [else (cons (f (first lst))                (my-map f (rest lst)))]))

Is this code telling racket to repeat until lst is empty?  Thx to all for your help.

---

From: Stephen Bloch <bl...@adelphi.edu>
To: Ronald Reynolds <bum...@bumpker.com>
Cc: racket list <us...@racket-lang.org>
Sent: Tuesday, June 5, 2012 5:57 AM
Subject: Re: [racket] recursion??

[Joshua Ewulo]

Hello Ronald,

Function calling is the semantically the same no matter what function you call. When you call a function you set up an environment/stack for the function to operate in.

Now when a function is recursive it create a new environment/stack and calls a function just like itself (with equivalent operational functionality) on the new environment/stack.

You could however simulate the contents of the new environment/stack using a single environment/stack by keeping track of the changing state explicitly in your code (i.e change the value of the current environment/stack within a loop say).

So, in a way it is true that you are making it repeat a loop but it is more semantically precise than that.

In some cases the recursive call makes the meaning/behaviour of the function clearer (eg: insertion-sort, quick-sort, merge-sort, tree traversals e.t.c). Try taking a look at implementations of the above that are not recursive and you will see what I mean.

I hope that helps.

Joshua Ewulo

[Stephen Bloch]

On Jun 6, 2012, at 6:17 AM, Ronald Reynolds wrote:

Is it correct to say that when I call a function inside of it's own definition I am just making it repeat loop?  

(define (my-map f lst)   (cond    [(empty? lst) empty]    [else (cons (f (first lst))                (my-map f (rest lst)))]))

Is this code telling racket to repeat until lst is empty?  Thx to all for your help.

In some cases, the effect is indeed similar to a repeat loop.  But I find function calling to be simpler and easier to understand than loops, so I would rather think of it the other way around: when you write a repeat loop, you are really doing a particularly simple form of recursion.  Any loop can be straightforwardly rewritten as a recursion, but many if not most examples of recursion CANNOT be straightforwardly rewritten as loops.

In other words, if you try to interpret every recursion as a loop, a lot of the examples simply won't fit into that mold.  You're better off thinking of recursion as calling a helper function which (by pure coincidence) happens to solve the same problem as the original function.

Let's re-develop "my-map" in terms of helper functions.  It's sometimes easier to solve a restricted version of a problem than the whole problem, so let's write a version that's only guaranteed to work on very short lists.

; my-map-0: does the same thing as my-map, but only guaranteed to work if lst is empty.

(define (my-map-0 f lst)

   (cond [(empty? lst) empty]

              [else (error 'my-map-0 "list too long")]))

Of course, that's not very useful, so let's write a version that works on SLIGHTLY longer lists.

; my-map-1: does the same thing as my-map, but only guaranteed to work if lst is at most one element.

(define (my-map-1 f lst)

   (cond [(empty? lst) empty]

              [else (cons (f (first lst)) (my-map-0 f (rest lst)))]))

; note that if lst is at most one element, then (rest lst) will be empty, so my-map-0 will work

; my-map-2: does th same thing as my-map, but only guaranteed to work if lst is at most two elements.

(define (my-map-2 f lst)

   (cond [(empty? lst) empty]

              [else (cons (f (first lst)) (my-map-1 f (rest lst)))]))

; note that if lst is at most two elements, then (rest lst) will be at most length 1, so my-map-1 will work

; my-map-3: does th same thing as my-map, but only guaranteed to work if lst is at most three elements.

(define (my-map-3 f lst)

   (cond [(empty? lst) empty]

              [else (cons (f (first lst)) (my-map-2 f (rest lst)))]))

; note that if lst is at most three elements, then (rest lst) will be at most length 2, so my-map-2 will work

And so on.  No recursion, just a bunch of helper functions, each of which solves "the same" problem, but is guaranteed to work on a different subset of cases.

Obviously, my-map-1, my-map-2, and my-map-3 all look extremely similar, so it would make sense to parameterize:

; my-map-n : does the same thing as my-map, but only guaranteed to work if lst is at most n elements.

(define (my-map-n n f lst)

   (cond [(empty? lst) empty]

              [else (cons (f (first lst)) (my-map-n (- n 1) f (rest lst)))]))

Then we notice that we're not actually USING n anywhere, so we might as well leave it out:

(define (my-map f lst)

   (cond [(empty? lst) empty]

              [else (cons (f (first lst)) (my-map f (rest lst)))]))

Stephen Bloch

sbl...@adelphi.edu

[Hendrik Boom]

On Wed, Jun 06, 2012 at 03:17:30AM -0700, Ronald Reynolds wrote:
> Is it correct to say that when I call a function inside of it's own
> definition I am just making it repeat loop?  
> (define (my-map f lst)
>   (cond
>    [(empty? lst) empty]
>    [else (cons (f (first lst))
>                (my-map f (rest lst)))]))
> Is this code telling racket to repeat until lst is empty?  Thx to all
> for your help. 
>

Yes, it does keep calling itself with smaller and smaller tails of the
original list until the list is empty.

And this part couldl be easily done in a loop.

But where this differs from a loop is that when all these functino calls
start returning. it does work on the way out -- all those cons'es. That
is more difficult to do with a loop.

-- hendrik

[David Janke]

Ronald,

The Structure and Interpretation of Computer Programs has a pretty good section about how the recursion happens. It's pretty short, and I think it covers what you are interested in understanding

http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-10.html#%_sec_1.1.5 

In particular, check out the "Applicative order versus normal order" sub-section and Exercise 1.5. It really helped me understand what's going on.