Recursion vs. Iteration

This is a discussion on Recursion vs. Iteration within the C++ Programming forums, part of the General Programming Boards category; Is there a worth-while benefit in performance to using recursion over iteration? I'm just really curious about the difference in ...

  1. #1
    Registered User
    Join Date
    Jul 2006
    Posts
    162

    Question Recursion vs. Iteration

    Is there a worth-while benefit in performance to using recursion over iteration? I'm just really curious about the difference in the methods during a 'heavy' process.

    I suppose the exact nature of the problem matters in determining Iteration vs. Recursion... so maybe someone can also elaborate on the border line decisions between the two. An obvious implementation would be in linked lists and binary tree's, but where's the 'line of preference' between these implementations and any other normal case where you'd typically think to use a loop for everyone?

    Obviously in Binary Tree's recursion produces cleaner code as well, and if that's the only real noticeable benefit then to me it's still worth-while. But what about in graphing functions in OpenGL? Whether that's a preferred method or not isn't in question, just from the performance aspect.

    Are there any ways in using recursion that typically a programmer may not think of? Anyone come up with some creative code and can offer some insight on testing with the methods?

    Thanks.

  2. #2
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    Typically, iteration is faster than recursion. You use recursion where it considerably simplifies the code.

    Clean code is more important than fast code. You can optimize the code when profiling shows that it's necessary.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  3. #3
    Registered User
    Join Date
    Oct 2001
    Posts
    2,129
    using recursion to traverse large data sets can crash your program. Each time a function call is made, it puts information onto the stack. Each time a function exits, a little information is taken off of the stack. Since stacks are not made large, typically, if you don't take calculated measures for code that makes a huge number of embedded function calls, you may end up with a stack overflow on your hands.

  4. #4
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >Is there a worth-while benefit in performance to using recursion over iteration?
    The general rule of thumb is that recursion gives you a performance hit, not a boost. That's not always the case, but it keeps the recursion happy freaks at bay.

    >but where's the 'line of preference' between these implementations and any other normal
    >case where you'd typically think to use a loop for everyone?
    If the iterative code is complicated, the recursive code is not complicated, and the recursive solution breaks down the problem by at least half with each call, you've got a good candidate for recursion. Anything less and I would question why you're not using loops.

    >Obviously in Binary Tree's recursion produces cleaner code as well
    That's where I'd disagree. I think that in many realistic tree implementations, recursion actually complicates the code and scrambles the logic. Compare the usual AVL insertion using recursion to a good implementation that doesn't. The passing and returning of information between recursive calls turns the code into a horrible mess.
    My best code is written with the delete key.

  5. #5
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,047
    I prefer not to use recursion, unless the iterative solution to a problem is very difficult to program.

    On the other hand, the (typical) performance hit induced by using recursion is usually irrelevant if the function will only recurse a few times.

    You should also be aware that some compilers can optimise recursive functions into iterative code. Don't count on this, but it can happen.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  6. #6
    Massively Single Player AverageSoftware's Avatar
    Join Date
    May 2007
    Location
    Buffalo, NY
    Posts
    141
    If you know ahead of time how many iterations/recursions you need, there are some nifty tricks using templates that can give you the functional convenience of recursion with the performance benefits of iteration. The better template metaprograms even produce unrolled loops from what appears to be a function call.
    There is no greater sign that a computing technology is worthless than the association of the word "solution" with it.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. iteration and recursion question
    By Stonehambey in forum C++ Programming
    Replies: 3
    Last Post: 03-19-2008, 06:16 PM
  2. Recursive function crashes.
    By samus250 in forum C Programming
    Replies: 9
    Last Post: 01-16-2008, 01:58 PM
  3. What is the difference between Recursion and Iteration?
    By neo_phyte in forum C Programming
    Replies: 12
    Last Post: 09-13-2006, 02:13 AM
  4. MPI - linear pipeline solution for jacobi iteration
    By eclipt in forum C++ Programming
    Replies: 1
    Last Post: 05-03-2006, 05:25 AM
  5. Iteration and recursion?
    By Munkey01 in forum C++ Programming
    Replies: 15
    Last Post: 01-18-2003, 07:16 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21