C++Talk.NET C++ language newsgroups   Archives   FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in to check your private messages   Log in  Question: How do you feel about recursion?          C++Talk.NET Forum Index -> C++ language (comp.lang.c++) View previous topic :: View next topic   Author Message da Vinci Guest Posted: Tue Oct 28, 2003 2:41 am    Post subject: Question: How do you feel about recursion? Greetings. I want to get everyone's opinion on the use of recursion. We covered it in class tonight and I want a good solid answer from people in the "know" on how well recursion is accepted in modern day applications. Should we readily use it when we can or only when absolutly forced to use it? I appreciate any responses. Just wanted to get a feel for it. I received a pretty dirty opinion of it tonight in class. Back to top Artie Gold Guest Posted: Tue Oct 28, 2003 3:17 am    Post subject: [OT] Re: Question: How do you feel about recursion? da Vinci wrote: Quote: Greetings. I want to get everyone's opinion on the use of recursion. We covered it in class tonight and I want a good solid answer from people in the "know" on how well recursion is accepted in modern day applications. Should we readily use it when we can or only when absolutly forced to use it? I appreciate any responses. Just wanted to get a feel for it. I received a pretty dirty opinion of it tonight in class. When a recursive solution is natural for a given problem -- and you know it is well bounded (i.e. will not get too deep) -- use it. If it proves to be a bottleneck (as discovered through profiling) you can always rewrite it as iteration. Some C++ compilers, in optimizing mode, can even transform some tail recursive algorithms into iteration by themselves. In any event, *understand* recursion. You may not use it in your actual code but it will quite likely inform your programming -- and improve it. That said, you're really off-topic here; please take your question to news:comp.programming. [f'ups set] HTH, --ag -- Artie Gold -- Austin, Texas Oh, for the good old days of regular old SPAM. Back to top David White Guest Posted: Tue Oct 28, 2003 3:20 am    Post subject: Re: Question: How do you feel about recursion? da Vinci <blank (AT) blank (DOT) com> wrote Quote: Greetings. I want to get everyone's opinion on the use of recursion. We covered it in class tonight and I want a good solid answer from people in the "know" on how well recursion is accepted in modern day applications. Anything that does a good job is acceptable. Recursion is no exception. You can't generalize about such things. Quote: Should we readily use it when we can or only when absolutly forced to use it? Use it if it's the best solution in the circumstances (where "best" can mean quickest or easiest to implement, easiest to understand, easiest to maintain, fastest to execute, etc. etc., whatever matters to you the most). Quote: I appreciate any responses. Just wanted to get a feel for it. I received a pretty dirty opinion of it tonight in class. To do something like searching for a file on a system with a nested directory structure, I would certainly do it with recursion because it's quick and easy to write and very effective. For something like a factorial calculation, which can be done recursively, a simple loop is probably much more effective. It really depends on what problem you want to solve. DW Back to top Gregg Guest Posted: Tue Oct 28, 2003 3:27 am    Post subject: Re: Question: How do you feel about recursion? da Vinci <blank (AT) blank (DOT) com> wrote in news:umlrpvkvt49u5t613tmskauii35tlse3g6 (AT) 4ax (DOT) com: Quote: Greetings. I want to get everyone's opinion on the use of recursion. We covered it in class tonight and I want a good solid answer from people in the "know" on how well recursion is accepted in modern day applications. Should we readily use it when we can or only when absolutly forced to use it? I appreciate any responses. Just wanted to get a feel for it. I received a pretty dirty opinion of it tonight in class. In some languages, recursion, especially tail recursion, is more natural than in others. In Lisp, for example, I think you would use recursion to implement what in other languages would be a simple loop. In a language like C++ you would normally use recursion only when an iterative solution would require implementing an explicit stack to store the algorithmic state. Since a stack is required anyway, might as well use the call stack if it simplifies the implementation. Traversing a tree structure would be an example of something best implemented recursively. The only caveat is the limited stack space some environments impose. Computational algorithms that are expressed as recurrence relations, such as Fibonocci sequence or factorial, are generally better implemented iteratively, since such an implementation does not require a stack, and so is simpler and faster done interatively. Gregg Back to top Andrey Tarasevich Guest Posted: Tue Oct 28, 2003 7:31 am    Post subject: Re: [OT] Question: How do you feel about recursion? da Vinci wrote: Quote: ... I want to get everyone's opinion on the use of recursion. We covered it in class tonight and I want a good solid answer from people in the "know" on how well recursion is accepted in modern day applications. Should we readily use it when we can or only when absolutly forced to use it? I appreciate any responses. Just wanted to get a feel for it. I received a pretty dirty opinion of it tonight in class. The term "recursion" has many different meanings, depending on the context. There is no point to start a debate about "recursion" without providing a clear definition for the term. What kind of recursion your question is about? Syntactical recursion, when one function in C or C++ program calls itself directly or indirectly? Algorithmical recursion, which implements stack-based version of 'divide & conquer' approach? Something else? -- Best regards, Andrey Tarasevich Brainbench C and C++ Programming MVP Back to top osmium Guest Posted: Tue Oct 28, 2003 1:45 pm    Post subject: Re: [OT] Question: How do you feel about recursion? Andrey Tarasevich writes: Quote: da Vinci wrote: ... I want to get everyone's opinion on the use of recursion. We covered it in class tonight and I want a good solid answer from people in the "know" on how well recursion is accepted in modern day applications. Should we readily use it when we can or only when absolutly forced to use it? I appreciate any responses. Just wanted to get a feel for it. I received a pretty dirty opinion of it tonight in class. The term "recursion" has many different meanings, depending on the context. There is no point to start a debate about "recursion" without providing a clear definition for the term. What kind of recursion your question is about? Syntactical recursion, when one function in C or C++ program calls itself directly or indirectly? Algorithmical recursion, which implements stack-based version of 'divide & conquer' approach? Something else? Jeez. Use recursion when it's natural. If its use strikes you as forced (as in factorial), it probably is. I would not want to code a tree or fiddle with the DOS file structure if I had a language that did not support recursion. The original languages, Cobol, Fortran and Basic could not "do" recursion. Your instructor might be from that era. Back to top jeffc Guest Posted: Tue Oct 28, 2003 3:25 pm    Post subject: Re: Question: How do you feel about recursion? "da Vinci" <blank (AT) blank (DOT) com> wrote Quote: Greetings. I want to get everyone's opinion on the use of recursion. We covered it in class tonight and I want a good solid answer from people in the "know" on how well recursion is accepted in modern day applications. Should we readily use it when we can or only when absolutly forced to use it? I appreciate any responses. Just wanted to get a feel for it. I received a pretty dirty opinion of it tonight in class. It's good for learning and making you think of new techniques. It does make certain problems much simpler, but in fact in general programming it's not often used. (I didn't say never.) Back to top chris Guest Posted: Tue Oct 28, 2003 4:35 pm    Post subject: Re: Question: How do you feel about recursion? da Vinci wrote: Quote: Greetings. I want to get everyone's opinion on the use of recursion. We covered it in class tonight and I want a good solid answer from people in the "know" on how well recursion is accepted in modern day applications. Should we readily use it when we can or only when absolutly forced to use it? I appreciate any responses. Just wanted to get a feel for it. I received a pretty dirty opinion of it tonight in class. You should recurse when you are doing something that naturally lends to it (seaching a tree, the main example you will come across in normal life is searching a hard disc). The overheard that comes from recursion unless you are doing 10,000s of levels is tiny, and almost certainly smaller than the improvement you would get with algorithms improvements. Also there is a good chance your attempts to avoid recursion will be less efficent than just doing it (this applies more and more with modern compilers) Back to top Jerry Coffin Guest Posted: Tue Oct 28, 2003 4:35 pm    Post subject: Re: Question: How do you feel about recursion? In article <umlrpvkvt49u5t613tmskauii35tlse3g6 (AT) 4ax (DOT) com>, [email]blank (AT) blank (DOT) com[/email] says... [ ... ] Quote: I want to get everyone's opinion on the use of recursion. That's a bit like asking "I want people's opinions of large trucks." It's so vague as to be nearly meaningless. Quote: Should we readily use it when we can or only when absolutly forced to use it? IMO, you should readily use it when doing so will lead to code that's easier to read and/or write than doing otherwise. Using it to create simple loops is pointless except in languages (e.g. LISP) that don't really support loops directly, or in situations (e.g. template meta- programming) where the language does, but not under the circumstances you care about. OTOH, there are also times that recursion seems to be a natural fit, but ends up working relatively poorly. Elsethread, traversing a tree-like file system has been mentioned, so I'll use it as well. The problem here is that traversing a tree-like file system recursively naturally tends to lead to a depth-first traversal, but this tends to make exceptionally poor use of caching. At least with all the OSes I've programmed, if you care much about speed, you're almost always better off doing a breadth-first traversal instead. This way, you read an entire directory at once, and then go to the next directory. This can avoid quite a bit of disk seeking as well as improving cache usage. The difference depends a lot on the directory structure, but if (for example) you were searching a large disk, a 10:1 speed improvement wouldn't be surprising at all. -- Later, Jerry. The universe is a figment of its own imagination. Back to top Andrey Tarasevich Guest Posted: Tue Oct 28, 2003 6:02 pm    Post subject: Re: [OT] Question: How do you feel about recursion? osmium wrote: Quote: ... The term "recursion" has many different meanings, depending on the context. There is no point to start a debate about "recursion" without providing a clear definition for the term. What kind of recursion your question is about? Syntactical recursion, when one function in C or C++ program calls itself directly or indirectly? Algorithmical recursion, which implements stack-based version of 'divide & conquer' approach? Something else? ... Use recursion when it's natural. If its use strikes you as forced (as in factorial), it probably is. I would not want to code a tree or fiddle with the DOS file structure if I had a language that did not support recursion. The original languages, Cobol, Fortran and Basic could not "do" recursion. ... Once again, the correctness of these statements greatly depends on the concrete meaning of the term "recursion" (and believe me, it has more than one). This has been discussed to death in more appropriate places. I don't see any reason to do it again here. -- Best regards, Andrey Tarasevich Brainbench C and C++ Programming MVP Back to top da Vinci Guest Posted: Tue Oct 28, 2003 7:41 pm    Post subject: Re: [OT] Question: How do you feel about recursion? On Tue, 28 Oct 2003 10:02:52 -0800, Andrey Tarasevich <andreytarasevich (AT) hotmail (DOT) com> wrote: Quote: Once again, the correctness of these statements greatly depends on the concrete meaning of the term "recursion" (and believe me, it has more than one). This has been discussed to death in more appropriate places. I don't see any reason to do it again here. Then lets not. I just learned it last night and with everything, I wanted the "pros" opinion on it. I wasn't aware there was more than one type as *I just learned it*. I was refering mainly to the fact of a function calling itself. I have made a few posts in the past regarding different issues and have been told by many people on the group that the way I was doing something was not accepted in the real world. I want to learn what IS acceptable. As I said, quite a few things I have learned already are actually NOT acceptable in the real world. So, I have curtailed my use of those practices on the advisement of group members. (The big one being that I was told that using the header call of #include <whatever.h> was perfectly fine to use in C++ and group members advised me otherwise.) So, this thread was begun with the intent to see if recursion is generally accepted or if it is shunned. I was unaware there are multiple meanings to recursion, other than just a function calling itself. Back to top MPBroida Guest Posted: Tue Oct 28, 2003 8:42 pm    Post subject: Re: Question: How do you feel about recursion? da Vinci wrote: Quote: Greetings. I want to get everyone's opinion on the use of recursion. It makes me feel good. And THAT makes me feel good. Which makes me feel good. <recurse ad nauseum> :) Back to top Alan Morgan Guest Posted: Tue Oct 28, 2003 10:46 pm    Post subject: Re: Question: How do you feel about recursion? In article <umlrpvkvt49u5t613tmskauii35tlse3g6 (AT) 4ax (DOT) com>, da Vinci <blank (AT) blank (DOT) com> wrote: Quote: Greetings. I want to get everyone's opinion on the use of recursion. The answers will probably be the same as if you asked everyone's opinions on linked lists. Recursion is a tool. It can be an obvious and good choice, an obvious and bad choice (using it to compute the nth Fibonacci number is an example of that), and one that is completely inapplicable to the problem. If it isn't in your bag of tricks you will be the poorer for it. If you use it everywhere it can be used then you will undoubtedly use it in places where it shouldn't be used. Alan -- Defendit numerus Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         C++Talk.NET Forum Index -> C++ language (comp.lang.c++) All times are GMT Page 1 of 1   Jump to: Select a forum C/C++----------------C LanguageC Language (Moderated)C++ Language (Moderated)C++ language (comp.lang.c++)C++ language, library and standards Non-English C/C++ Newsgroups----------------C++ (German)C++ (French)  You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum Powered by phpBB © 2001, 2006 phpBB Group SEO toolkit © 2004-2006 webmedic.