# [plt-scheme] HtDP newbie question, 12.4.2

 From: Cooke Kelsey (cookekelsey at yahoo.com) Date: Sun Mar 30 21:42:02 EDT 2008 Previous message: [plt-scheme] HtDP newbie question, 12.4.2 Next message: [plt-scheme] HtDP newbie question, 12.4.2 Messages sorted by: [date] [thread] [subject] [author]

```Hi Marco

Everything you told me makes perfect sense to me now.  I just wasn't used to the idea of recursion.

I can picture a function with one recursion is something.  I picture the inputs cycling back to the top of the function, one by one, like people riding a Ferris wheel.  The syntax still looks kind of paradoxical to me, but I can say, OK it's just circling around.

Two recursions, on the other hand, are totally beyond me.  My mind just goes blank.  I realize that I should try to think of each function separately, but it is still very confusing.

You gave me the following advice, which ALMOST did the trick:

"Here is where I believe you are really stuck....How do you insert a letter everywhere in (rest a-word)? Once you have this list (call it R) all you need is to do something with (first a-word).  Where does it have to go in each of R?"

When you said, "call it R," I did get a sort of picture in my mind of the result of the recursion as a unit, a thing, instead of all these arrows going around in circles all over the place.

Then, in your last email, you basically gave me the answer by saying:
"It is easy to do using (add-letter-to-all  <letter><list-of-words>). What you need now is to create all the words possible from letter and (rest a-word)."

At that point it became clear to me how I could plug in "insert...(rest word)" into <list-of-words>, just like any list.

I personally think that Matthias's idea of tables is probably the best way to explain these recursive helper functions.

The problem was that he didn't really explain the fourth table to me.   Hopefully in HtDP/2 he will flesh it out like the way you explained it.  Section 12.2 could include an introduction like this:

"This section is about Recursive Auxiliary functions.  We have already used basic recursion in functions that process lists.  Now we are going to use recursive helper functions inside other recursive functions.

"For example, A-Function is constructed with a recursive expression--A-Function (rest X)--that is input into a helper function, A-Helper, like this:

(define (A-Function X)
(...(first X)...(A-Helper (A-Function (rest X)))

"The inputs to A-Function may pass through 2 or more recursive functions.  For such complex problems, it is useful to use a table...."

...And explain clearly what the fourth column of the table is all about.

cooke

In fact, I should have figured it already from reading Section 12.2, Recursive Auxiliary Functions, which introduces the concept which got me stuck.

Unfortunately, the Section only explains it indirectly through the problem of "insertion sort":

"Inserting a number into a sorted list isn't a simple task. We may have to search through the entire list before we know what the proper place is. Searching through a list, however, can be done only with a function, because lists are of arbitrary size and processing such values requires recursive functions."

In retrospect, this paragraph could have been enough to get me through 12.4.2, but at the time it just did not impress on me the enormous leap I would have to make in my mind.

Marco Morazan <morazanm at gmail.com> wrote:
Dear Cooke,

I am delighted that you solved the problem. Well done! :-)

I also thank you for that summary of your thoughts through the
process. They provide me with insight as to what kind of advice works
and what those who are stuck are thinking.

I am curious, however, about one more thing regarding the
comments/ideas I provided to you. In one of my messages (the last one
I believe), I tried to explain to you (in mostly prose) how the
problem was decomposed into simpler and simpler problems. Was that
useful at all? Did it complement the tables you were creating well or
was that too abstract to be useful?

Thanks,

Marco

---------------------------------
Like movies? Here's a limited-time offer: Blockbuster Total Access for one month at no cost.
-------------- next part --------------
An HTML attachment was scrubbed...