Path: utzoo!attcan!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!zephyr.ens.tek.com!uw-beaver!ubc-cs!manis
From: manis@cs.ubc.ca (Vincent Manis)
Newsgroups: comp.edu
Subject: Re: Recursion?
Message-ID: <9919@ubc-cs.UUCP>
Date: 7 Oct 90 19:57:50 GMT
References: <1990Oct5.101354.593@contact.uucp>
Sender: news@cs.ubc.ca
Distribution: na
Organization: Institute for Pure and Applied Eschatology
Lines: 46

Well, since Cobol's PERFORM statement is just a special case of
recursion[1], albeit with delusions of grandeur, he's been using
recursion all the time, without knowing it.[2]

Here are my top ten fave applications of recursion:

1) Printing an integer in minimum width. A recursive PDP-11 assembly
language implementation of C's itoa library routine was measured as
running faster than its iterative counterpart.

2) Inserting a key into a binary search tree. The recursive
implementation lends itself to various `hooks,' of which AVL insertion
is the best known. Iterative deletion is possible, but horrendously
messy. 

3) Quicksort. Tony Hoare's Turing lecture points out what a mess the
code was before he was encouraged to rewrite it in Algol 60. Even though
one tries not to be *too* recursive about it (eliminating tail recursion
in Quicksort is definitely a Good Thing), an even partially recursive
version is much clearer (and no slower, on reasonable hardware) than a
completely iterative one.

4) Recursive descent parsing. Still the one of the best (though not
quite the fastest) parsing techniques. Recursive descent parsers are
used in a number of production compilers, because almost any grammar is
LL(1), and therefore can be translated almost literally into one's
favourite programming language. (And one doesn't need an ungulate plains
beast such as Yacc or Bison to assist.) 

5) Symbolic mathematics. Doing a derivative or integral with a program
such as Macsyma or Mathematica necessarily involves a fair bit of
recursion.

Your Cobol friend might find none of these interesting, but they are
most definitely *real*.

-----
[1] see Guy Steele's `Lambda: The Ultimate Imperative,' MIT AI Memo ca.
1975, or Abelson & Sussman's `Structure and Interpretation of Computer
Programs.' 
[2] cf. Moliere's `Le Bourgeois Gentilhomme.' 
--
\    Vincent Manis <manis@cs.ubc.ca>      "There is no law that vulgarity and
 \   Department of Computer Science      literary excellence cannot coexist."
 /\  University of British Columbia                        -- A. Trevor Hodge
/  \ Vancouver, BC, Canada V6T 1W5 (604) 228-2394