mac (03/24/83)
Recursion is a very powerful control structure. Learning to use recursion
may indeed be harder than learning iteration. Figuring out what a highly
recursive program does can often be difficult.
However, most uses of recursion fall into a few special cases. One of
these is iteration. Languages such as VAL, LISP and SCHEME provide nice
syntactic forms (macros, if you will) to describe the iterative forms of
recursion, and to allow the user to recognize them.
This is like the special form (FOR) of the WHILE loop provided by many
languages, which makes explicit the varying of an arithmetic variable over
some range. It saves programmer, compiler, and reader trouble.
Other special cases of recursion with simple properties are tree traversal,
backtracking, game tree exploration, and set closure under some set of
transformations. Few languages have any convenient notation for these.
Non-recursive languages have highly inconvenient notation for these --
nearly all the code is concerned with doing recursion the hard way, almost
none with the actual operation.
My argument here is that programming languages should provide recursion,
AND provide ways to indicate the simple cases of it. Good macros are one
way. Another (but usually syntactically messier) is functional languages
which can pass operations and data structures to a function that applies
one to the other in some systematic way.
One of the nice features of SCHEME (and ISWIM) (and not LISP) is that a
recursive function must be explicitly so. A recursive function, or a set
of mutually recursive functions, must be defined with the LABELS (or LET
REC) construct to allow the forward references necessary for recursion.
"I call myself"
Alex Colvin
usenet: ...{decvax,harpo}!duke!mcnc!ncsu!uvacs!mac
csnet: mac@virginia
arpa: mac.uvacs@udel-relay