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.