Problem with recursion? (was [plt-scheme] Re: Novice, needs help writing function )

From: Prabhakar Ragde (plragde at
Date: Sun Jan 6 13:46:57 EST 2008

Richard Cobbe wrote:

> One of the major strengths of the HtDP model, IMO, is the emphasis it
> places on examples -- both of data structures and of functions.  Among
> other things, this forces students (and professors, for that matter) to
> approach generalizations from the concrete.  Most of us, myself included,
> aren't so different from the child in the story above in that respect.

I would suggest the opposite -- that HtDP encourages one to develop in 
generality, as opposed to just about every other approach, which 
presents a bunch of examples and then leaves students to form their own 
(possibly imperfect) generalizations. As the book proceeds, fewer 
examples are used. Before each of the data definitions for ancestor and 
descendant family trees, there is exactly one example. There is no 
example presented before the data definition for binary trees. Templates 
encourage students to proceed from the general to the specific.

As for the difficulty of recursion, it is not the concrete nature of 
data structures that makes recursion on them easier. The non-negative 
integers are pretty concrete, also. But students have had much 
experience working with the non-negative integers in a non-recursive 
fashion, whereas this is not true for lists and trees. This novelty 
provides sufficient motivation for recursion, and the substitution model 
which needs no change or augmentation to work for recursive functions 
provides proper support to understand the mechanism.

I find it amusing that section 9 of HtDP tiptoes into both 
self-referential data definitions and recursive functions, whereas 
section 8.2 presents a Scheme grammar, naturally self-referential, with 
absolutely no fanfare or fuss. --PR

Posted on the users mailing list.