Thread: Loops or recursive functions?

  1. #1
    Registered User
    Join Date
    Nov 2007
    Posts
    48

    Loops or recursive functions?

    hi everyone. Often we have two possibilities for getting a task done: we do it by looping or we can do it by writing a recursive function. About efficience, what is the best way?

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Use a loop since recursion would impose the overhead of having to save the current state, and consequently there is typically some maximum limit to the number of levels of recursion that could reasonably be reached.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Typically prefer recursion if you can't do it in any efficient way through iteration.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  4. #4
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by mariano_donati View Post
    hi everyone. Often we have two possibilities for getting a task done: we do it by looping or we can do it by writing a recursive function. About efficience, what is the best way?
    You should prefer loops by default, but there are exceptions:

    * The problem domain is naturally recursive and not deep -- for instance, game tree search
    * The iterative version would be extremely hard to write
    * The iterative version would be extremely hard to understand.

    Unless you have one of these cases, use a loop.

  5. #5
    Registered User
    Join Date
    Nov 2007
    Posts
    48
    Thanks for your answers. Do you know any tutorial about C efficience in wich issues like this are covered?

  6. #6
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by mariano_donati View Post
    Thanks for your answers. Do you know any tutorial about C efficience in wich issues like this are covered?
    Not aware of any tutorial, but you should be aware that the compiler is nearly always good at optimizing loops. It will only sometimes make sense out of recursive algorithms (real simple cases can usually be turned into loops anyways).

    If the compiler can't make the recursion into a plain loop, then it's almost certainly at the very least two instructions [the call that takes you to the next level of recursion, and the return to get back again] longer (thus slower) to use recursion [exceptions do exist - and I can't think of any example where those are not also in the "exceptions" listed by Brewbuck].

    Further, deep recursion, or recursion with lots of state on the stack [large local variables] is inherently dangerous, since the running out of stack is "catastrophic" - so you need some way to prevent overflwoing the stack, by knowing that you will never recurse more than x levels.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Static member functions more efficient?
    By drrngrvy in forum C++ Programming
    Replies: 6
    Last Post: 06-16-2006, 07:07 AM
  2. Recursive Functions
    By jack999 in forum C++ Programming
    Replies: 8
    Last Post: 06-07-2006, 01:28 PM
  3. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  4. writing functions
    By jlmac2001 in forum C++ Programming
    Replies: 5
    Last Post: 09-20-2003, 12:06 AM
  5. need help with recursive functions
    By datainjector in forum C Programming
    Replies: 3
    Last Post: 07-18-2002, 07:32 PM