| About a month ago I was looking for clues on something -- I think I was seeking information on implementations of "bitset" -- when I ran across the following post. > From: "Phobos" > Newsgroups: alt.comp.lang.learn.c-c++ > Sent: Friday, May 11, 2001 2:23 PM > Subject: [C++] Iteration and Recursion > <Greetings> > I'm in the process of learning C++ and I came across the interesting topic of Iteration and Recursion, given that recursion creates new instances of variables every time that the function is called (thereby using memory etc.) > I was wondering if anyone had an example of when recursion would be preferable to iteration? > Or even an opinion on the subject... > > P I attempted to reply directly to the sender rather than muck up the list with my long-winded comments since it would appear that there's no way of getting a short answer from me. I have the incredibly good habit of supplying context, background and thorough description with the notion that the recipient may not be psychic, may be thinking of an entirely different subject or may have forgotten why I'm sending an essay on this or that by the time s/he sifts through the queue of messages ahead of mine, but for some reason, some people find a detailed report offensive. Personally, I read about 2K words/minute but I only write about 80 or 90 wpm at the most -- and I don't see the economy in replying to me in a diatribe on the length of my message. Anyway, the poster apparently used a bogus address and my reply bounced. I was really disappointed that I didn't get the chance to share my opinion which was really on the order of free professional advice. There may be some imprecision in the way I expressed myself in the reply, so I still didn't want to post to the list and receive a barrage of technical criticism, so I sent it to a colleague who might appreciate the material. After our discussion, I began to be more comfortable with the idea of posting it to my journal, then archiving it and gradually promoting it and modifying it (on the basis of feedback, if I get it) until it is fit for publication in my Software Development Notes section. To encourage me to change my way of thinking, this is the message that Roger sent me: ----------- begin message -------- From: "Roger Guisinger"<rguisinger@email.root> To: <ernie.cordell@computer.org> Sent: Sunday, June 10, 2001 5:48 PM This is good stuff. I would reply to him via the group, saying you have a lot to say about recursion but don't want to publish to the group, and establish an off-line dialogue. You might invite group members who are interested to join the off-line dialogue. You might publish it to your website, for example. ----------- end message ----------- [I agreed with his comment and sent him a reply like this.] It was one of these "news-web-posts" and I hit reply deciding that would be what I would do if I got a newsgroup-post reply, but if I got an Email address, I'd go ahead and answer the guy. [I thought of reposting but by that time I wasn't sure] in which newsgroup I found it: I was originally reading alt.comp.lang.learn.c-c++, but you know how web versions of newsreaders are -- you can jump off into another discussion without even knowing it. [I didn't want to search just to find it when it was] not a nice way to treat people whose aid he wishes to enlist. [I wanted to supply the information for other people on the list, but at that point I would be sacrificing potential income as well as time.] So I wrote: Posting it to my website is an interesting thought -- it might be a good thing for Software Development Note #n+1. I would want to clean it up first, though. [I was at first concerned with the time it would take me to convert this message to HTML and I was worried that] I'd immediately be flamed for any imprecisions, especially if I put it on a published page. An overpowering thought was: I should try to put a little more time into web content development. [I explained that I had lost a good biography that I had written for my web pages when] I hit the "Save" button, Microsoft Windows [failed], my disk crashed and that was the only file that didn't survive [after] I recovered as much as possible. [I was particularly disappointed because I felt that] It would have completely put to rest [the argument] about "not having any apparent focus [in my career path]." It showed what my objectives were, all the steps that I took in my approach to solve the problems that were important to me, how many of my milestones that I hit . . . . [I was discouraged by how much I had accomplished without a computer and how little I was accomplishing with one, but I was optimistic enough to end with the light-hearted comment] -- Comedy is easy; Emotional Adjustment is hard . . . Earlier I had written: [After explaining how the message had bounced,] I thought you might be interested in my response to him, though, because it addresses recursion not only as a programming technique, with efficiency concerns, but with design and business concerns as well. I enclosed the "essay" on iteration versus recursion which is the core topic of this website posting: Subject: Re: [C++] Iteration and Recursion Date: Sun, 10 Jun 2001 13:15:05 -0400 Organization: Ernie's Place I often find the decision as to whether to post to the group somewhat difficult. Many people have opinions, and in this case, I'm one of them. You might [want to] think of recursion as an "expanding scope" problem: The invocation record that has to be resolved in order for the function to return is replicated, consuming more and more memory. But the last-generation element has to be resolved before it can be returned to the previous invocation. This does mean that a "variable" is being replicated, but in each recursion that "variable" may hold a different value, altering the way in which each recursion is executed: It has its own memory, and in a sense, its own scope. Once the final recursion leaves its scope, it releases its memory (in a well-behaved implementation) and returns its result to the previous recursion. So the memory usage expands and collapses like an accordion: It is effectively a way of invoking the same function with different parameter values -- something that you would be doing with iteration anyway. The difference is the kind and number of copies of that function (or its invocation record) that you would have in memory at the same time. You might also think of it as a set of invocation records for a series of functions that are all pushed onto a stack, and popped off and resolved until the original caller is satisfied. This is roughly the kind of operation that you have in a parsing operation in the best of situations. The difference here is whether we're pushing operators and operands or function parameters and invocation records. Also, data structures (a tree, for instance) may behave in much the same way: A process builds a tree from the root to the leaves; as each of the leaves of the tree are resolved, the nodes are removed and their values are returned to the parents of these nodes until the tree has collapsed to produce some sort of unified result. You may think of the way parsing trees are built as an example. Parses or algorithms that use this "expansion and collapse" to "intermediately compute and resolve" an inductive-like series may often lend themselves to recursion. If it is simpler to use iteration, iteration may be more desireable. The "bad" form of recursion is "uncontrolled." Like an infinite loop, no exit is found -- but worse, it will continue to consume memory until there is an abort, or still worse, crash the operating system or the machine (depending on where it goes for this memory). "Good" recursion, like the Prolog AI routines use, always have a point at which they "bail." This is usually because there is no need to continue in order to resolve: Imagine a scenario where there is a successive approximation conducted. At some point the approximation will exceed the precision given deltas and tolerances, or maybe just machine precision capacity. Prolog uses what is called a "cut element" to halt the recursion (at which the algorithm "collapses in on itself," steadily decreasing its memory use). This corresponds to the "if clause" of a well-written recursion -- > > > if (bail-point) > > > return args > > > else > > > call-me(n-times); > > > So there is an efficiency consideration for recursion: A recursion should be limited in what it can and will accept as arguments to be workable. It should be known (roughly) how many invocation records will be pushed and what kind of time and space resources will be used unwinding the stack afterwards. Another way of looking at the decision as to whether to use recursion is whether determination of the parameters to a function depend upon a previous invocation of that function. It might be a bit egg-headed to seek a function that not only returns the result that you want, but also determines a succession of parameter values. Binary growth and collapse might tend in that direction, but only a few problem sets will naturally suggest recursion. Now that we have talked about the decision to use recursion in terms of programming solutions and efficiency, let me suggest something I consider much more important: Business solutions. If the recursion is simple, direct and controlled, it may well be coded in many fewer lines than comparable iterative solutions. If the solution is simple, direct, controlled, clear and can be placed in a single cognitive block, it may be easier to maintain. Sometimes efficiency takes a back seat to labor cost: If the recursive solution takes one page of code and "ten pages in memory," it may make sense to pay a programmer once for a recursive solution rather than pay many programmers for many hours maintaining iterative solutions that do not naturally derive their parameters, but rather rely on other functions to find those parameters for them. If you would like an exercise that demonstrates this, write a program as though it were intended for a language that does not support recursion; then simulate recursion using iteration. It's better to conduct this experiment than to listen to me, but I think you'll find that simulating recursion proves more complicated than using it in the first place. This is the heart of the business maintenance cost argument: Recursion is good when it avoids complexity that increases production cost. [Recognizing that I eliminated little confusion and introduced some imprecision I signed off on the reply with] I hope this doesn't muddy the waters too much -- Ernie Another colleague of mine (Bob Schaab) once launched a defense for my E-mail messages, "People always react kinda funny when they get their first Erniegram (aside: that's what I call Ernie's E-mails). When I got my first Erniegram, I thought -- What the heck is this guy tryin' ta say? -- but then I read the message again and I understood. He's just tryin' ta tell people what he thinks they oughta know -- what he'd like to know -- before startin' ta work on a problem." When I put together what Roger and Bob have said, I decided that it would be better to publish this -- if anybody has any thoughts on improving it, I'll try to incorporate comments into another version that I will eventually post under the Software Development Notes section. Until then, don't get angry, consider this entry "an essay on probation" and I'll attempt to make it "right and good" in your eyes, too. End of current rant and rave . . . posted at 11:39:50 PM by Ernie Cordell I found a number of interesting links at The Proceedings of the Friesian School on Tuesday (July 3rd). Intrestingly enough, I stumbled onto it when I watched the movie "The Matrix" and the form of the Latin Expression "Temet Nosce" troubled me (the form of Gnothi Seauton still troubles me, because I've long thought it should be Gnate Se-auton, but that's another story). The site's Ownership, Copyright, & Disclaimer says: The Proceedings of the Friesian School, Fourth Series is a non-periodic journal and archive of philosophy, updated as needed, published and edited by Kelley L. Ross, Ph.D.. All materials, unless otherwise indicated, are copyrighted (c) 1979, 1985, 1987, 1996, 1997, 1998, 1999, 2000, 2001 by the editor. All rights are reserved, but fair and good faith use with attribution may be made of all contents for any non-commercial educational, scholarly, and personal purposes, including reposting, with links to the original page, on the internet. It is not necessary to obtain copyright release for such uses, but the Proceedings would be grateful to be voluntarily informed, for informational purposes only, of the use of its materials. Commercial use of these materials may not be made without written permission. So if anyone has a presence of mind to do so, tell them that I have posted this and I would have informed them, but I likely forgot because my mind was a jumble as I rambled through links and blogs trying to bring as much useful material to light as possible. I found the quote on this website, but I was intrigued in that a number of well-written, informed and clear-thinking articles were posted to this site, and a few of them were: The Matrix -- A legitimate criticism of the horror that was supposed to be a mainstream, published review of the movie where it was pretty evident that the reviewer didn't even see the film. More credit was given to that reviewer, noting that "he surely wasn't paying attention" in this splendid article that is bound to add to the numerous interpretations that one fancies while watching the film that manages to combine action, adventure, science fiction, martial arts, doomsday projections and fairly deep metaphysical questions about the nature of reality. To my mind, both movie and article answer well the issue of the "brain in a vat" concept which troubles critics of "The Cartesian Theatre" as we continue to explore the nature of that which we might call "Sentient Consciousness." Basic Buddhist Teachings and Doctrines is the best "nutshell explanations" that I've ever seen on the belief system, history and genesis of this religion. It fairly thoroughly delineates basic thoughts and precepts that are core to the philosophical base of Buddhism, and makes a good "side read" to the application of Buddhist thought in "The Matrix ." Carl Gustav Jung is also a good synopsis of Jung's thought and even includes other links that show other earlier sources for the derivation of such concepts as "Archetypes of the Collective Unconscious." Rudolf Otto is one such selection, showing that mystical features of Jung's expositions on synchronicity can be seen as extensions of "numinosity" that is common to every belief system that holds certain objects or persons "special" in the sense that they are regarded as "holy" or "sacred." Excuse my occasionally poor descriptions (and maybe even erroneous ones in subtle distinctions that escape me) here, since I'm trying to draw emphasis to the links that I mention and present them for people to follow, not trying replace them or reiterate them elsewhere. I found them interesting because (1) they pulled together threads on the meaning of "Temet Nosce" which I'm more accustomed to seeing in the context of the Delphic Oracle (and hence in Greek); (2) they featured an article on "The Matrix" that added "meat" to my perceptions on the nature of reality exposed in the film; (3) the article on the movie showed the lengths to which some critics will go after having seen only the trailer for a film; and (4) there are good, substantive explanations of notions in philosophy that can edify and instruct casual layperson and intellectual savant alike. posted at 2:50:23 PM by Ernie Cordell This is a test: God, I hate writing this, but I'm tired of writing long test entries, and at this point I don't want to save an entry to cut and paste over again. With my luck, this one will work -- and I'll hate looking at it from aeons to come.
posted at 1:18:09 PM by Ernie Cordell | 
