C++Talk.NET C++ language newsgroups   Archives   FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in to check your private messages   Log in  Recursion Goto page 1, 2  Next          C++Talk.NET Forum Index -> C++ Language (Moderated) View previous topic :: View next topic   Author Message Orjan Westin Guest Posted: Sat Mar 12, 2005 2:10 am    Post subject: Recursion Just had an idle thought the other day. I'm old enough to have cut my teeth on non-OO programming, in C, Pascal and Modula-2. A standard advice was always "do not recurse, for an full stack easily offends", which is fair enough. In a recursive call, just like any other function call, the current context plus return address is pushed onto the stack, but since recursive calls can be very deep without seeming to be so it's a high risk the stack will take a beating, especially if the recursive function context has a lot of big data. So far so good. But surely class recursion must be a lot cheaper? If the data that would, in C for instance, be local variables/function parameters is actually member data of the class, there ought to be a lot less strain on the stack, since only "this", any local variables and the return address needs be stored. Have I missed something here, or does this mean I don't have to look furtively over my shoulder before putting in a recursive call in a class, and that I don't need to hide it in a brown paper bag? Orjan -- Get your Tale paperback or CD here: http://tale.cunobaros.com Or just read it there, if you don't want the illustrations [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Victor Bazarov Guest Posted: Sat Mar 12, 2005 11:35 am    Post subject: Re: Recursion "Orjan Westin" <nospam (AT) cunobaros (DOT) demon.co.uk> wrote... Quote: Just had an idle thought the other day. I'm old enough to have cut my teeth on non-OO programming, in C, Pascal and Modula-2. A standard advice was always "do not recurse, for an full stack easily offends", which is fair enough. In a recursive call, just like any other function call, the current context plus return address is pushed onto the stack, but since recursive calls can be very deep without seeming to be so it's a high risk the stack will take a beating, especially if the recursive function context has a lot of big data. So far so good. But surely class recursion must be a lot cheaper? If the data that would, in C for instance, be local variables/function parameters is actually member data of the class, there ought to be a lot less strain on the stack, since only "this", any local variables and the return address needs be stored. Have I missed something here, or does this mean I don't have to look furtively over my shoulder before putting in a recursive call in a class, and that I don't need to hide it in a brown paper bag? Essentially what you're saying is right, however, it would be basically the same if in Pascal, C, whatever, instead of keeping the state in the local variables, you'd have another function argument, a struct (a record, or whatever) where you'd keep the state. OTOH, if you in a class member function have lots of automatic variables, you still would have the same problem as in C or Pascal -- any recursive call would generate new ones. So, IMO, nothing changed. Certain things just have become a bit more obvious and data (and functionality) repackaging into classes pushed us towards making slightly different decisions than before... V [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Mark Van Peteghem Guest Posted: Sat Mar 12, 2005 11:38 am    Post subject: Re: Recursion Orjan Westin wrote: Quote: Just had an idle thought the other day. I'm old enough to have cut my teeth on non-OO programming, in C, Pascal and Modula-2. A standard advice was always "do not recurse, for an full stack easily offends", which is fair enough. In a recursive call, just like any other function call, the current context plus return address is pushed onto the stack, but since recursive calls can be very deep without seeming to be so it's a high risk the stack will take a beating, especially if the recursive function context has a lot of big data. So far so good. But surely class recursion must be a lot cheaper? If the data that would, in C for instance, be local variables/function parameters is actually member data of the class, there ought to be a lot less strain on the stack, since only "this", any local variables and the return address needs be stored. Less data on the stack would mean it is faster. But in many recursive functions, a modified value is passed, like in the well known example to calculate the factorial: int factorial(int n) { if (n==0) return 1; else return n*factorial(n-1); } If n were the member of a class, you could define a member function factorial, but you would only have an advantage if you decremented n on every call to factorial, and later increment it again. This looks ugly to me, and factorial can't be const, although it could be faster. For other examples where a lot of unmodified data is passed, the picture might look better. -- Mark dot Van dot Peteghem at q-mentum dot com http://www.q-mentum.com -- easier and more powerful unit testing [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Antoun Kanawati Guest Posted: Sat Mar 12, 2005 11:38 am    Post subject: Re: Recursion Orjan Westin wrote: Quote: Just had an idle thought the other day. I'm old enough to have cut my teeth on non-OO programming, in C, Pascal and Modula-2. A standard advice was always "do not recurse, for an full stack easily offends", which is fair enough. In a recursive call, just like any other function call, the current context plus return address is pushed onto the stack, but since recursive calls can be very deep without seeming to be so it's a high risk the stack will take a beating, especially if the recursive function context has a lot of big data. So far so good. But surely class recursion must be a lot cheaper? If the data that would, in C for instance, be local variables/function parameters is actually member data of the class, there ought to be a lot less strain on the stack, since only "this", any local variables and the return address needs be stored. You got the basics right. But, the efficiency issues with recursion are not only about stack size. The other efficiency issue is the cost of procedure calls. This depends on architecture, compiler and compilation options, but it is generally more expensive that a straight forward loop. Quote: Have I missed something here, or does this mean I don't have to look furtively over my shoulder before putting in a recursive call in a class, and that I don't need to hide it in a brown paper bag? OK, the facts of life are: C++ is not tuned for recursion; in Scheme, for example, there is only the procedure call and tail-call elimination, and you loop by writing recursive code. In C++, recursion and looping are very different. So, you have to pay some attention to the matter. And, that's about it. The recursion-hostile attitude is outdated. Recursion is beautiful, and there is no reason to avoid recursion out-of-hand. -- A. Kanawati [email]NO.antounk.SPAM (AT) comcast (DOT) net[/email] [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Ivan Vecerina Guest Posted: Sat Mar 12, 2005 7:59 pm    Post subject: Re: Recursion "Orjan Westin" <nospam (AT) cunobaros (DOT) demon.co.uk> wrote Quote: Just had an idle thought the other day. I'm old enough to have cut my teeth on non-OO programming, in C, Pascal and Modula-2. A standard advice was always "do not recurse, for an full stack easily offends", which is fair enough. In a recursive call, just like any other function call, the current context plus return address is pushed onto the stack, but since recursive calls can be very deep without seeming to be so it's a high risk the stack will take a beating, especially if the recursive function context has a lot of big data. High risk only if you're not sure how deep the recursion may go. Quote: So far so good. But surely class recursion must be a lot cheaper? If the data that would, in C for instance, be local variables/function parameters is actually member data of the class, there ought to be a lot less strain on the stack, since only "this", any local variables and the return address needs be stored. If a large data context is shared during recusion, it obviously makes sense to pass down a single pointer or reference rather than copying the data as a parameter to each call. In OO, this data block can be an object instance -- but that's barely anything new in terms of recursion. Quote: Have I missed something here, or does this mean I don't have to look furtively over my shoulder before putting in a recursive call in a class, and that I don't need to hide it in a brown paper bag? Recursions has its pitfalls, but there are a number of nails for which it is indeed the right hammer. Also, most desktop systems today have as much stack space (even for threads) as older computers had in total RAM, so stack usage is less of an issue today. In most cases, you're safe if you avoid any expensive local data, and know that you won't recurse any deeper than log(itemCount). [ And if one doesn't know how to balance a tree, avoiding recursion won't be enough to keep performance problems at bay. ] Also, some C++ compilers have gotten good at optimizing-out recursion, for inline functions and tail recursion in particular. [ Tail recursion is when the calling function ends with a (resursive) call: the compiler can then jump back to the beginning of the function, or recycle the current stack frame and - so to speak - use a "JMP" instead of a "JSR" ]. This said, in low-level library code (e.g. STL routines, image processing primitimes, etc), it is still common in C++ to manually "derecursify" algorithms to optimize performance. Cheers, Ivan -- http://ivan.vecerina.com/contact/?subject=NG_POST <- email contact form [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Dave Harris Guest Posted: Mon Mar 14, 2005 12:07 am    Post subject: Re: Recursion [email]INVALID_use_webform_instead (AT) vecerina (DOT) com[/email] (Ivan Vecerina) wrote (abridged): Quote: Also, some C++ compilers have gotten good at optimizing-out recursion, for inline functions and tail recursion in particular. [ Tail recursion is when the calling function ends with a (resursive) call: the compiler can then jump back to the beginning of the function, or recycle the current stack frame and - so to speak - use a "JMP" instead of a "JSR" ]. I imagine tail recursion is relatively rare in idiomatic C++, because it is defeated by auto destructors. For example: void print( int n ) { if (n > 0) { std::string s( "Hello, world" ); cout << s; print( --n ); } } this is not tail-recursive because the string's destructor gets called after the recursive call to print(). So I am mildly surprised that any C++ vendors have bothered to optimise tail recursion. It's not something I'd rely on. -- Dave Harris, Nottingham, UK [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top James Kanze Guest Posted: Mon Mar 14, 2005 1:01 am    Post subject: Re: Recursion Antoun Kanawati wrote: [...] Quote: The other efficiency issue is the cost of procedure calls. This depends on architecture, compiler and compilation options, but it is generally more expensive that a straight forward loop. On the other hand, it's often cheaper than the alternatives, when recursion isn't used for just a simple loop. Quote: Have I missed something here, or does this mean I don't have to look furtively over my shoulder before putting in a recursive call in a class, and that I don't need to hide it in a brown paper bag? OK, the facts of life are: C++ is not tuned for recursion; in Scheme, for example, there is only the procedure call and tail-call elimination, and you loop by writing recursive code. More to the point, using recursion when a loop would do the job isn't idiomatic C++. Compilers could do tail-call elimination as an optimization; they generally don't because C++ programmers don't use recursion in such cases, so the time spent trying to find the optimizations which aren't there would be wasted. -- James Kanze home: www.gabi-soft.fr Conseils en informatique orientée objet/ Beratung in objektorientierter Datenverarbeitung 9 pl. Pierre Sémard, 78210 St.-Cyr-l'École, France +33 (0)1 30 23 00 34 [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Orjan Westin Guest Posted: Mon Mar 14, 2005 8:58 am    Post subject: Re: Recursion Antoun Kanawati wrote: Quote: Orjan Westin wrote: Just had an idle thought the other day. I'm old enough to have cut my teeth on non-OO programming, in C, Pascal and Modula-2. A standard advice was always "do not recurse, for an full stack easily offends", which is fair enough. In a recursive call, just like any other function call, the current context plus return address is pushed onto the stack, but since recursive calls can be very deep without seeming to be so it's a high risk the stack will take a beating, especially if the recursive function context has a lot of big data. So far so good. But surely class recursion must be a lot cheaper? If the data that would, in C for instance, be local variables/function parameters is actually member data of the class, there ought to be a lot less strain on the stack, since only "this", any local variables and the return address needs be stored. You got the basics right. But, the efficiency issues with recursion are not only about stack size. The other efficiency issue is the cost of procedure calls. This depends on architecture, compiler and compilation options, but it is generally more expensive that a straight forward loop. Yes, but if the loop also requires a procedure call? I can see situations where the number of function calls would be the same for a recursive and a looped implementation. The difference would be that the loop version would have each call return before it's called again, whereas a recursive approach would first do all calls and then the returns. In such a situation, it's just the stack size that speaks against recursion, since with all pertinent data as class members it would be comparable to sending an object reference to a function. Orjan [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Orjan Westin Guest Posted: Mon Mar 14, 2005 9:00 am    Post subject: Re: Recursion Victor Bazarov wrote: Quote: "Orjan Westin" <nospam (AT) cunobaros (DOT) demon.co.uk> wrote... So far so good. But surely class recursion must be a lot cheaper? If the data that would, in C for instance, be local variables/function parameters is actually member data of the class, there ought to be a lot less strain on the stack, since only "this", any local variables and the return address needs be stored. Essentially what you're saying is right, however, it would be basically the same if in Pascal, C, whatever, instead of keeping the state in the local variables, you'd have another function argument, a struct (a record, or whatever) where you'd keep the state. Yes, certainly. However, this suffers from the same problem as the pimpl idiom, in that while it hides implementation details from the compiler, it also hides it from the programmer. There are situations where a recursive call is the most elegant and readable thing to do, and to do so within the context of a class makes it obvious where the data manipulated by the function comes from. Pretty much anything you would care to do with recursion can be done with a loop, sometimes managing a separate stack for the data, but when a recursive call is what expresses the intent best I would prefer to use it, simply because I code for humans, not compilers. Efficiency is something I worry about when I have to, but expressive code is important when you can expect it to live for a long time and be used and maintained by many different programmers. Quote: OTOH, if you in a class member function have lots of automatic variables, you still would have the same problem as in C or Pascal -- any recursive call would generate new ones. Yes, of course. Quote: So, IMO, nothing changed. Certain things just have become a bit more obvious Exactly! That's the point I wanted to make. The penalty for a recursive and expressive call is typically less in C++ than in C. Orjan [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Antoun Kanawati Guest Posted: Mon Mar 14, 2005 9:03 am    Post subject: Re: Recursion James Kanze wrote: Quote: Antoun Kanawati wrote: The other efficiency issue is the cost of procedure calls. This depends on architecture, compiler and compilation options, but it is generally more expensive that a straight forward loop. On the other hand, it's often cheaper than the alternatives, when recursion isn't used for just a simple loop. Tail-call self recursion is essentially a loop. So, obviously overt looping is faster than that recursive form. The other kind of recursion is algorithmically convertible to stack-and-loop form. So, if you open-code the stack operations, or make sure that they are inlined, it is possible to reduce the procedure call overhead associated with the recursive form. In the second case, I stick to the recursive form, unless I have some red-hot profile saying I need to do something about it. Quote: OK, the facts of life are: C++ is not tuned for recursion; in Scheme, for example, there is only the procedure call and tail-call elimination, and you loop by writing recursive code. More to the point, using recursion when a loop would do the job isn't idiomatic C++. Compilers could do tail-call elimination as an optimization; they generally don't because C++ programmers don't use recursion in such cases, so the time spent trying to find the optimizations which aren't there would be wasted. This is a matter of perspective. The recursion purist would argue that looping idioms exist to compensate for faulty implemenetations of procedure calls. Is looping idiomatic because we can't recurse efficiently? or is recursion not fully optimized because looping is an idiom? I "grew up" on Programming Languages theory and Scheme, so I never got quite comfortable with loops as a "real" programming construct. But, that's just my personal quirk. -- A. Kanawati [email]NO.antounk.SPAM (AT) comcast (DOT) net[/email] [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Ivan Vecerina Guest Posted: Mon Mar 14, 2005 1:32 pm    Post subject: Re: Recursion "Dave Harris" <brangdon (AT) cix (DOT) co.uk> wrote Quote: INVALID_use_webform_instead (AT) vecerina (DOT) com (Ivan Vecerina) wrote (abridged): Also, some C++ compilers have gotten good at optimizing-out recursion, for inline functions and tail recursion in particular. [ Tail recursion is when the calling function ends with a (resursive) call: the compiler can then jump back to the beginning of the function, or recycle the current stack frame and - so to speak - use a "JMP" instead of a "JSR" ]. I imagine tail recursion is relatively rare in idiomatic C++, because it is defeated by auto destructors. .... So I am mildly surprised that any C++ vendors have bothered to optimise tail recursion. It's not something I'd rely on. Many C++ compilers share a back-end with another language (C or more), and it is this processor-specific back-end that would perform tail recursion optimization. This said, I agree that I wouldn't rely on it - nor even care about it before getting to a profiling stage. Ivan -- http://ivan.vecerina.com/contact/?subject=NG_POST <- email contact form [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top ThosRTanner Guest Posted: Mon Mar 14, 2005 9:33 pm    Post subject: Re: Recursion Dave Harris wrote: Quote: So I am mildly surprised that any C++ vendors have bothered to optimise tail recursion. It's not something I'd rely on. It may be something from existing C compiler code that has been lifted when implementing the C++ compiler. After all, it's not difficult to recognise tail recursion. I've also heard that under some circumstances C compilers produce better code for optimised-out tail recursion than they do for a loop. Certainly the scuttlebut round here is that an implementation of strcmp that used tail recursion produced faster code than a normal loop. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Ismail Pazarbasi Guest Posted: Mon Mar 14, 2005 11:56 pm    Post subject: Re: Recursion I agree with your comment's last part. However, I am quite unsure about first part concerning compiler architecture. I apologize, if I misunderstood the concern (no offence); a C++ compiler wouldn't try to perform optimization with C-ish manner. As far as I know, today's C++ compilers always tend to spare C and C++ logics. After all, these are two different languages, although C is ancestor of C++. Dave exposed a good case. That's not a tail recursion, because object's destructor will be called after print(), and compiler thinks in C++. Recursion is still utile, and sometimes the first solution arose among others. Developer should make a decision, and take the risk of diving to an unknown depth into account before using recursion. Ismail [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Gabriel Dos Reis Guest Posted: Tue Mar 15, 2005 8:30 pm    Post subject: Re: Recursion "Ismail Pazarbasi" <pazarbasi (AT) gmail (DOT) com> writes: Quote: I agree with your comment's last part. However, I am quite unsure about first part concerning compiler architecture. I apologize, if I misunderstood the concern (no offence); a C++ compiler wouldn't try to perform optimization with C-ish manner. As far as I know, today's C++ My understanding is that it is quite commcon. Quote: compilers always tend to spare C and C++ logics. After all, these are two different languages, although C is ancestor of C++. yet, the pratice is that C-specific logic is often carried straight to C++. For good or bad. -- Gabriel Dos Reis [email]gdr (AT) integrable-solutions (DOT) net[/email] [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Gabriel Dos Reis Guest Posted: Tue Mar 15, 2005 8:31 pm    Post subject: Re: Recursion Antoun Kanawati <antounk (AT) comcast (DOT) net> writes: [...] Quote: OK, the facts of life are: C++ is not tuned for recursion; in Scheme, for example, there is only the procedure call and tail-call elimination, and you loop by writing recursive code. More to the point, using recursion when a loop would do the job isn't idiomatic C++. Compilers could do tail-call elimination as an optimization; they generally don't because C++ programmers don't use recursion in such cases, so the time spent trying to find the optimizations which aren't there would be wasted. This is a matter of perspective. The recursion purist would argue that looping idioms exist to compensate for faulty implemenetations of procedure calls. Is looping idiomatic because we can't recurse efficiently? or is recursion not fully optimized because looping is an idiom? I "grew up" on Programming Languages theory and Scheme, so I never got quite comfortable with loops as a "real" programming construct. But, that's just my personal quirk. On correctness side, it is my belief that for many cases, it is easier to prove the correctness of "the" recursive form than that of the iterative form. But, I guess it depends on ones mind twist. -- Gabriel Dos Reis [email]gdr (AT) integrable-solutions (DOT) net[/email] [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] 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 (Moderated) All times are GMT Goto page 1, 2  Next Page 1 of 2   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.