[racket] recursion?? two

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

On 6 June 2012 11:17, Ronald Reynolds <bumpker at bumpker.com> 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<http://docs.racket-lang.org/reference/define.html#(form._((lib._racket/private/base..rkt)._define))>
>  (my-map f lst)  (cond<http://docs.racket-lang.org/reference/if.html#(form._((lib._racket/private/letstx-scheme..rkt)._cond))>
>    [(empty?<http://docs.racket-lang.org/reference/pairs.html#(def._((lib._racket/list..rkt)._empty~3f))>
>  lst) empty<http://docs.racket-lang.org/reference/pairs.html#(def._((lib._racket/list..rkt)._empty))>
> ]   [else<http://docs.racket-lang.org/reference/if.html#(form._((lib._racket/private/letstx-scheme..rkt)._else))>
>  (cons<http://docs.racket-lang.org/reference/pairs.html#(def._((quote._~23~25kernel)._cons))>
>  (f (first<http://docs.racket-lang.org/reference/pairs.html#(def._((lib._racket/list..rkt)._first))>
>  lst))               (my-map f (rest<http://docs.racket-lang.org/reference/pairs.html#(def._((lib._racket/list..rkt)._rest))>
>  lst)))]))
>  Is this code telling racket to repeat until lst is empty?  Thx to all for
> your help.
>
>   ------------------------------
> *From:* Stephen Bloch <bloch at adelphi.edu>
> *To:* Ronald Reynolds <bumpker at bumpker.com>
> *Cc:* racket list <users at racket-lang.org>
> *Sent:* Tuesday, June 5, 2012 5:57 AM
> *Subject:* Re: [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
>
>
>
>
> ____________________
>  Racket Users list:
>  http://lists.racket-lang.org/users
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20120606/68efaeb5/attachment.html>