Recursion and structure (aka Shriram's quiz)

[Benderjg2@aol.com]

I often use factorial (in either the tree recursive or tail recursive form) 
as a basic test of a new interpreter or compiler. It tells me that recursion 
"worked".

However, when I look at my own _programming_, it is recursion over a data 
structure, especially lists, which I use most. With respect to SICP, which is 
far more numerical in its orientation--at least in early chapters--than my 
own programming: factorial would not be how I would teach recursion in the 
first week(s) of an introductory programming course.

One great beauty of Scheme/Lisp is that I can teach someone to build a list 
from the beginning. From there, the structure of the data leads to the 
structure of a function processing that data structure. I would feel guilty 
if I did not show a recursive structure for traversing/processing that list. 
Thus my own answer to this question is that I would teach construction of 
lists _with_ recursive traversal of those lists. That would be how I would 
teach recursion. [I must grant that I am not a teacher.]

(With respect to whether one teaches while/for/repeat/do-style iteration 
constructs before recursion, I can not help but feel that the _language_ 
taught often shapes what is an "advanced" topic in this country's intro CS 
courses. Recursion over a linked list in Pascal (which I had for intro CS) or 
C/C++ is tough. One first has to know memory management. One also has to know 
about struct or classes--i.e. about "complicated" mechanisms for creating 
data structures. In C/C++/Pascal, iteration over an array is the only _easy_ 
structure that can be taught. Another sad fact is that, while that iteration 
over an array _could_ be taught as tail recursion, for/while/do/repeat is 
used because it is "fast"/"cheap", while recusion is "slow"/"expensive".)

jim

[Jim Bender (benderjg@aol.com)]



In a message dated 1/27/01 10:15:27 PM Central Standard Time, 
mvanier@bbb.caltech.edu writes:


> > > Even recursion is an advanced topic, and thanksfully nobody is
> > > forced to write recursive in lisp/scheme.
> > 
> > Quick quiz: If you had to teach recursion, what is the first example
> > you would use?  (You may give multiple examples, but they must all be
> > ones you would cover in the first week of teaching it.)
> > 
> > Shriram
> > 
>
> Factorial, no doubt.  The way it's handled in SICP is particularly elegant,
> contrasting the obviously recursive way of writing factorial e.g.
>
> (define (factorial n)
>   (if (= n 1)
>       1
>       (* n (factorial (- n 1)))))
>
> with the tail-recursive way:
>
> (define (factorial n)
>   (define (fact-iter n r)
>     (if (= n 1)
>         r
>         (fact-iter (- n 1) (* r n))))
>   (fact-iter n 1))