Thread: Recursion... why?

  1. #1
    Its hard... But im here swgh's Avatar
    Join Date
    Apr 2005
    Location
    England
    Posts
    1,688

    Recursion... why?

    After reading the chapter on Recursion in my book, it posed a very interesting statement:

    Recursion has many negatives. It repeatedly invokes the mechanism, and consequently the overhead, of function calls. This can be both expensive in both processor time and memory space. Each recursive call causes another copy of the function variables to be created, this can comsume considerable memory.

    Iteration normally occurs within the function, so the overhead of repeated function calls and extra memory assignment is omited.

    So, why choose recursion?
    I understand it is all about choosing the right style for the job in hand, so why teach me somthing when it is deemed as bad to do? Im interested to know if what they have told me is somthing I need to look at, and avoid recursion in my programs.
    Double Helix STL

  2. #2
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Some problems are more naturally solved with recursion (though this may depend on the coder).

    For example quicksort:
    Code:
    def quicksort(range):
         lower, upper = partition(range)
         if lower:
              quicksort(lower)
         if upper:
              quicksort(higher)
    Recursion is convenient because it manages the stack of ranges to sort for you.

    On the other hand, there probably isn't much point to using recursion for things which might be more simply done with a loop (e.g calculating factorial - since there is no stack to maintain).
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  3. #3
    Registered User
    Join Date
    Apr 2006
    Posts
    2,149
    Recursion should be avoided except in a few broadly applicable cases:
    1)When the number of iterations is consistently small and recursion appears to describe the solution susinctly.
    2)When writing an algorithm to work without recursion would be unduly complex, and result in hard to follow code.
    3)When the algorithm is naturally recursive, such that all local variables are necessary to copy into a stack anyway, and the function overhead therefore countered by equivalent iterative measures.

    So in general, you should avoid recursion. But there are cases where recursion offers simpler solutions, so its something to keep in mind.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  4. #4
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Recursion is one tool that can be a choice for certain types of problems, as explained above.

    Knowing when and where to use which tool is part of learning to program. Part of that is of course understanding the consequences of the choice of a particular method or tool. If you have a heavy, big hammer, it will get nails into a piece of wood very easily. But if you have small panel tacks (little nails, less than 2cm long), then a 5lbs sledge-hammer is not the right choice. On the other hand, when you want to take down a wall, a 5+lbs hammer is exactly what you want/need (and the tiny one that is suitable for the little nails will NOT work).

    --
    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.

  5. #5
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by swgh View Post
    I understand it is all about choosing the right style for the job in hand, so why teach me somthing when it is deemed as bad to do? Im interested to know if what they have told me is somthing I need to look at, and avoid recursion in my programs.
    It's really a language-specific question. Most functional languages have no loops, which means everything is recursion. The question to pose yourself is "Should I use recursion for this task when I'm programming in C/C++?" EDIT: Point being, in many languages you have no choice whether to use recursion. So the rule "Avoid it unless impossible" is really too general. From a CS standpoint, recursion is a better description of problems than iteration. If we lived in a perfect world (infinitely fast machines, infinite memory), then recursion would always be preferable, hands down.

    There are data structures (e.g. trees) which are recursive, and the algorithms which process these data structures are recursive as well. It's usually possible to "unwrap" recursion into plain iteration, but the code often becomes more confusing. Is it worth the additional complexity in return for performance? Sometimes it is, sometimes not. And if the recursive structures are amazingly deep, you can run out of stack space if you try to process them recursively.

    It takes experience.
    Last edited by brewbuck; 06-09-2008 at 09:46 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Template Recursion Pickle
    By SevenThunders in forum C++ Programming
    Replies: 20
    Last Post: 02-05-2009, 09:45 PM
  2. a simple recursion question
    By tetra in forum C++ Programming
    Replies: 6
    Last Post: 10-27-2002, 10:56 AM
  3. stack and recursion help needed!
    By LouB in forum C++ Programming
    Replies: 3
    Last Post: 07-01-2002, 02:19 PM
  4. To Recur(sion) or to Iterate?That is the question
    By jasrajva in forum C Programming
    Replies: 4
    Last Post: 11-07-2001, 09:24 AM
  5. selection sorting using going-down and going-up recursion
    By Unregistered in forum C Programming
    Replies: 1
    Last Post: 11-02-2001, 02:29 PM