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." |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.