Question: How do you feel about recursion?

Discussion in 'C++' started by da Vinci, Oct 28, 2003.

  1. da Vinci

    da Vinci Guest

    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.
     
    da Vinci, Oct 28, 2003
    #1
    1. Advertisements

  2. da Vinci

    Artie Gold Guest

    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, Oct 28, 2003
    #2
    1. Advertisements

  3. da Vinci

    David White Guest

    Anything that does a good job is acceptable. Recursion is no exception. You
    can't generalize about such things.
    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).
    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
     
    David White, Oct 28, 2003
    #3
  4. da Vinci

    Gregg Guest

    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
     
    Gregg, Oct 28, 2003
    #4
  5. 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?
     
    Andrey Tarasevich, Oct 28, 2003
    #5
  6. da Vinci

    osmium Guest

    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.
     
    osmium, Oct 28, 2003
    #6
  7. da Vinci

    jeffc Guest

    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.)
     
    jeffc, Oct 28, 2003
    #7
  8. da Vinci

    chris Guest

    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)
     
    chris, Oct 28, 2003
    #8
  9. da Vinci

    Jerry Coffin Guest

    [ ... ]
    That's a bit like asking "I want people's opinions of large trucks."
    It's so vague as to be nearly meaningless.
    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.
     
    Jerry Coffin, Oct 28, 2003
    #9
  10. 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.
     
    Andrey Tarasevich, Oct 28, 2003
    #10
  11. da Vinci

    da Vinci Guest

    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.
     
    da Vinci, Oct 28, 2003
    #11
  12. da Vinci

    MPBroida Guest

    It makes me feel good.
    And THAT makes me feel good.
    Which makes me feel good.
    <recurse ad nauseum>

    :)
     
    MPBroida, Oct 28, 2003
    #12
  13. da Vinci

    Alan Morgan Guest

    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
     
    Alan Morgan, Oct 28, 2003
    #13
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.