[comp.edu] Recursion?

rrwood@contact.uucp (roy wood) (10/05/90)

I'm working with someone whose background is mostly COBOL programming in
a business environment.  This person is convinced that recursion is just
a "trick" of some sort, with no real world applications.  I'm trying to
think of some examples that really show the usefulness of recursion,
but all I can think of right now are factorials and the knight's tour
problem.  Does anyone out there know of any other good examples that
show the reak usefulness of recursion?
 
-Roy Wood.

psmielke@lotus.uwaterloo.ca (Peter Mielke) (10/06/90)

In <1990Oct5.101354.593@contact.uucp>, rrwood@contact.uucp (roy wood) writes:
> I'm working with someone whose background is mostly COBOL programming in
> a business environment.  This person is convinced that recursion is just
> a "trick" of some sort, with no real world applications.  I'm trying to
> think of some examples that really show the usefulness of recursion,
> but all I can think of right now are factorials and the knight's tour
> problem.  Does anyone out there know of any other good examples that
> show the reak usefulness of recursion?

Think of grammars that specify computer languages.. Or, natural
language grammars. Granted we humans don't go to the same sort of
depth of recursion than computers.

Give him a Prolog manual for Christmas! :-)

> -Roy Wood.

Peter.
--
Peter Mielke                     Preferred ->  psmielke@lotus.waterloo.edu
University of Waterloo                         peter@doe.utoronto.ca
An undergrad that's been around too long...

kanamori@Neon.Stanford.EDU (Atsushi Kanamori) (10/06/90)

In article <1990Oct5.101354.593@contact.uucp> rrwood@contact.uucp (roy wood) writes:
>
>Does anyone out there know of any other good examples that
>show the reak usefulness of recursion?

Dunno about business environments but as for reek (er, real) uses
of recursion: 

  processing nested #include directives in C files,
  evaluating arithmetic expressions, 
  recursive descent parsing,
  maintaining binary search trees (or any kind of tree),
  implementing quicksort.

That should do it.

gvcormack@watdragon.waterloo.edu (Gordon V. Cormack) (10/06/90)

Generating all permutations (or substrings) of a string is a
simply stated problem that justifies recursion.

Traversing a hierarchical database is less simply stated, but
may appeal to COBOL programmers.
-- 
Gordon V. Cormack     CS Dept, University of Waterloo, Canada N2L 3G1
gvcormack@waterloo.EDU  gvcormack@uwaterloo.CA  gvcormac@water.BITNET

geoffw@xenitec.on.ca (Geoffrey Welsh) (10/06/90)

In article <1990Oct5.101354.593@contact.uucp> rrwood@contact.uucp (roy wood) writes:
>Does anyone out there know of any other good examples that
>show the reak usefulness of recursion?

   The Towers of Hanoi.

UUCP:     watmath!xenitec!zswamp!root | 602-66 Mooregate Crescent
Internet: root@zswamp.fidonet.org     | Kitchener, Ontario
FidoNet:  SYSOP, 1:221/171            | N2M 5E6 CANADA
Data:     (519) 742-8939              | (519) 741-9553
My comments do not represent and should not obligate anyone but myself.

wiml@milton.u.washington.edu (William Lewis) (10/07/90)

In article <1990Oct05.221120.25060@xenitec.on.ca> root@zswamp.fidonet.org (Geoffrey Welsh) writes:
>In article <1990Oct5.101354.593@contact.uucp> rrwood@contact.uucp (roy wood) writes:
>>Does anyone out there know of any other good examples that
>>show the reak usefulness of recursion?
>
>   The Towers of Hanoi.

   Actually, the iterative solution to the Towers is probably faster on
most machines, takes less memory (no stack required), and generates
exactly the same moves as the recursive version (in fact, I first
noticed it by watching the output from a recursive solver.) The
iterative solution is:

  1. Move disk 1 (the small disk) to the right (or to the leftmost pin
if it's already on the rightmost).
  2. Move something else.
  3. Repeat until done.

    and yes, there's always only one move possible in step 2. It's easy to
see that if you start doing it this way and then deviate, you're going
backwards. Dunno if that constitutes a proof of optimality or anything =8)


    not to speak against recursion, of course. But *some* recursive solutions
have "better" iterative solutions. (Although it seems that recursive solutions
are usually easier to understand; it's more obvious why they're correct...)

-- 
 wiml@milton.acs.washington.edu       Seattle, Washington   
     (William Lewis)   |  47 41' 15" N   122 42' 58" W  
"These 2 cents will cost the net thousands upon thousands of 
dollars to send everywhere. Are you sure you want to do this?"

nmouawad@water.waterloo.edu (Naji Mouawad) (10/07/90)

Speaking of recursion, here's a little thing to ponder ...

Traversing an ordered binary tree recursively is easy (Depth first say)
Doing the same job using a stack is equally easy (takes more time to
write down).
How's about traversing a tree with a constant number of pointers ?

Heh, heh ...

---Naji.

-- 
         ---------------+-------------------------------------------
        | Naji Mouawad  |       nmouawad@water.waterloo.edu         |
        |  University   |-------------------------------------------|
        | Of Waterloo   | "Thanks God, we cannot prove He Exists."  |

manis@cs.ubc.ca (Vincent Manis) (10/08/90)

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

manis@cs.ubc.ca (Vincent Manis) (10/08/90)

Oops! I got interrupted after posting five of my top 10 fave
applications of recursion. I leave the remaining ones as an exercise for
the reader. 

--
\    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

rbutterworth@watmath.waterloo.edu (Ray Butterworth) (10/09/90)

To make Thanksgiving dinner:
    For each required course or ingredient, pick one:
       - buy it.
       - take it out of the cupboard, or fridge, or whatever.
       - use a recipe and make it.
The last step says to divide the requirement up into its components
and recursively apply the same algorithm to each one.

robert@cs.arizona.edu (Robert J. Drabek) (10/10/90)

Naji Mouawad writes:
> Speaking of recursion, here's a little thing to ponder ...
> 
> Traversing an ordered binary tree recursively is easy (Depth first say)
> Doing the same job using a stack is equally easy (takes more time to
> write down).
> How's about traversing a tree with a constant number of pointers ?
> 

Threaded trees.  They can even be written without the extra flag.
See Information Processing Letters, Vol 26, Number 4, 8 Nov. 1986:
Eliminating the flag in threaded binary sort trees; Dan Gordon.

-- 
Robert J. Drabek                            robert@cs.Arizona.EDU
Department of Computer Science              uunet!arizona!robert
The University of Arizona                   602 621 4326
Tucson, AZ  85721

asylvain@felix.UUCP (Alvin E. Sylvain) (10/11/90)

In article <1990Oct5.101354.593@contact.uucp> rrwood@contact.uucp
Roy Wood writes:
::
::I'm working with someone whose background is mostly COBOL programming in
::a business environment.  This person is convinced that recursion is just
::a "trick" of some sort, with no real world applications.  I'm trying to
::think of some examples that really show the usefulness of recursion,
::but all I can think of right now are factorials and the knight's tour
::problem.  Does anyone out there know of any other good examples that
::show the reak usefulness of recursion?
:: 
::-Roy Wood.

Judging by the responses you gotten so far, and anything I think of which
isn't much better, I'd say your chances of convincing this fellow are
pretty slim.  It would seem that the "real world" for business computing
is somewhat different than the "real world" for compiler writing, automata
theory, artificial intelligence, list processing, database processing, and
infinite other fields of computer science.

Just tell him it's a tool like anything else.  A person who never drives
in the backwoods will probably not have much use for a winch on his 4x4,
or even a 4x4 for that matter.  Consider recursion as a tool, which has
it's proper applications.  Accounts Receiveables just ain't one of 'em.
--
=======================Standard Disclaimers Apply=======================
"We're sorry, but the reality you have dialed is no   |            Alvin
longer in service.  Please check the value of pi,     |   "the Chipmunk"
or pray to your local diety for assistance."          |          Sylvain
= = = = = =I haven't the smoggiest notion what my address is!= = = = = =

louk@tslwat.UUCP (Lou Kates) (10/13/90)

In article <152256@felix.UUCP> asylvain@felix.UUCP (Alvin "the Chipmunk" Sylvain) writes:
>In article <1990Oct5.101354.593@contact.uucp> rrwood@contact.uucp
>Roy Wood writes:
>::problem.  Does anyone out there know of any other good examples that
>::show the reak usefulness of recursion?
>or even a 4x4 for that matter.  Consider recursion as a tool, which has
>it's proper applications.  Accounts Receiveables just ain't one of 'em.

Accounts   could    be  aggregates  of   other  accounts so  that
accumulating the tree   of  accounts  under a particular  account
could be done recursively. There exists  an    accounting program
called NewViews  whose user interface which consists of exploding
accounts into subaccounts makes this rather obvious.

An inventory  parts  system for   a manufacturer might have parts
which are  actually assemblies of other parts.  A complete  parts
breakdown  of  a   particular   assembly   part could be done  by
recursively traversing  the tree of parts   that     the assembly
represents.   

Look for  applications  that require  what data processing people
call "explosion" and you will likely find additional applications
for recursion.

Unfortunately, the  business community and  those who cater to it
have traditionally held the view that recursion is not applicable
to these problems. This is reinforced the lack of availability of
recursion in the first  place as a  tool to this group since  the
most widely used tools for business data processing are COBOL and
SQL and  both  lack the ability to do  recursion. When innovative
applications like NewViews come  along which expose the naturally
recursive  structure of certain business applications it tends to
be a great surprise to many.

Lou Kates, Teleride Sage Ltd., louk@tslwat, 416-596-1940 ext. 210

clayc@ssds.com (Clay Calhoun) (10/15/90)

You might also look at accounting programs which talk about consolidation.