[plt-scheme] Re: Novice needs help writing function

On Dec 30, 2007, at 8:02 PM, dave yrueta wrote:

> I'm looking for a text which, first and foremost, attempts to explain
> recursion from a naive point of view -- that is, from the perspective
> of someone who is encountering it for the first time (by the way, I
> think HtDP does a very good job of this).

and

> I've ordered a book by a Standford CS prof named Eric Roberts called
> "Thinking Recursively," whose description seems tailored to needs like
> mine.

In that case, my answer is HtDP, no smileys no nothing. Work through
chapters II, III, and V.


> The concluding exercises consisted of about 20
> problems on arrays but only one on recursion -- Hanoi Towers -- which
> nearly drove me to seek out the top of their physical counterparts for
> a place to leap from.  My feeling is that the solution to the Hanoi
> Towers problem is of a much higher order of complexity than solving
> factorials, and that the move from one to the other, in the context of
> an introductory educational text, was unjustified.

You are absolutely correct. There is a huge distinction between
recursion based on data and recursion based on ad hoc insights:
  -- see chapters II and III
  -- versus chapter V

BTW, while II is ostensibly about "lists" this is not so at
all. While III appears to discuss "trees" or S-expressions,
this is just a running example.

"Exercise: Design a program that undresses a Russian doll (RD).
The result is the number of layers that you have to remove
before you get to the naked doll.

To make life simple, the data definition of RD is included:

  RD is one of:
  -- 'naked
  -- (cons RD empty)"

This is a typical (of course non-PC) exercise that I assign
in class after one or two lectures on chapter II.

> So the second thing I'm looking for is a text which is sensitive to
> this issue, and at least makes an attempt to discern levels of
> complexity among the classes of problems suited for recursive
> solutions.

HtDP.

;; ---


BTW, Your problem is about natural numbers, which is the super
imposition of a recursive view on an enumerated type (numbers):

A Nat is one of:
  -- 0
  -- (add1 Nat)

The selector for add1-numbers is sub1. The predicate is zero?.
Since you studied philosophy, you should be intimately familiar
with this; it is the only datatype logicians know.

;; ---

Last but not least, keep in mind that HtDP is an expansion of
The Little Schemer, nee Little LISPer (MIT Press).

-- Matthias, co-philosophy student