Recursion help

This is a discussion on Recursion help within the C++ Programming forums, part of the General Programming Boards category; Hi Can anyone explain to me what recursion really is why and where you would use it - if possible ...

  1. #1
    Is Trying to Learn
    Join Date
    Mar 2006
    Location
    Hutton, Preston
    Posts
    215

    Recursion help

    Hi

    Can anyone explain to me what recursion really is why and where you would use it - if possible why would you use it rather than a loop cause that is all i am aware of what it does at the moment saying that it is similar to a loop.

    can anyone help?

    Thanks

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,415
    Read the tutorial on recursion.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Jul 2006
    Posts
    162
    fractals ... linked lists... trees of all sorts... etc...


    "what recursion really is":
    Code:
    void Hey! (string hi)
    {
    	cout << hi << endl;
    	Hey! (hi);
    }
    
    Hey! ("hi!");
    hahah

    recursion is a loop... it might just make the code a lot cleaner... i hear it's not as efficient as other loops maybe? i forget, i made a thread on it once... i'll try and go dig it up.
    Last edited by simpleid; 08-21-2007 at 12:25 PM.

  4. #4
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    Do you know what a tree looks like? I'm referring to a tree in computing, not a real tree. Maybe something like this:
    Code:
                           a
                         / | \
                        b  c  d
                       / \     \
                      e   f     g
                     /   / \   / \
                    h   i   j k   l
    Now, let's say you want to process the nodes of the tree. One easy way to break it down is to start at the root, and process each of the root's subtree's. So from a, you have these three subtrees:
    Code:
                        b          c          d
                       / \                     \
                      e   f                     g
                     /   / \                   / \
                    h   i   j                 k   l
    It should be easy to process c, you just do what you need to do with that node. But how do you process b? Again, separating each subtree makes sense, so you have:
    Code:
                      e         f
                     /         / \
                    h         i   j
    Notice how the task keeps getting broken down into smaller and smaller task, but each smaller task is handled the same way as the big task. If the root node has children, process the children, then process the node. When you write the code, it just makes sense to have a function that does that and doesn't care whether it is working on the whole tree or a subtree. It will just keep recursing on smaller and smaller subtrees until it finishes the whole thing.

    That's what recursion is for. When you can break a problem down into smaller, identical problems.

  5. #5
    Registered User
    Join Date
    Oct 2001
    Posts
    2,129
    Quote Originally Posted by simpleid View Post
    recursion is a loop... it might just make the code a lot cleaner... i hear it's not as efficient as other loops maybe?
    this will crash:
    Code:
    #include <iostream>
    #include <string>
    
    void Hey(std::string hi)
    {
        std::cout << hi << std::endl;
        Hey(hi);
        return;
    }
    
    int main()
    {
        Hey("hi!");
        return 0;
    }
    this doesn't:
    Code:
    #include <iostream>
    #include <string>
    
    void Hey(std::string hi)
    {
        while (1)
            std::cout << hi << std::endl;
        return;
    }
    
    int main()
    {
        Hey("hi!");
        return 0;
    }
    Last edited by robwhit; 08-21-2007 at 01:07 PM. Reason: dwks -Wall -Werror file.cpp

  6. #6
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046
    Not neccesarily. Some compilers can actually optimise recursive functions into iterative loops, or so I hear.
    [edit]
    Question #49

    When run on a computer, will a recursive function without an end condition ever quit?
    Compiler-Specific (Some compilers can convert these functions to infinite loops)
    No
    Yes
    From http://www.cprogramming.com/ans/ans5.html [/edit]

    Besides, neither should compile, unless you include <string>. And use std::cout, std::endl, and std::string, or a using directive or three.

    [edit=2] As for efficiency . . . iterative loops are generally considered to be more efficient than recursive functions. With recursive functions, there's a speed hit as the function is called, and of course memory usage on the stack as a result, with extra memory usage if the function has any local variables.

    However, sometimes an iterative solution to a problem might be so convoluted or inefficient or hard to read that a recursive solution might be better.

    Personally, I don't see anything wrong with writing recursive functions if they solve a problem easily. (Unless the iterative solution is very trivial.) You can always try an iterative solution later. [/edit]
    Last edited by dwks; 08-21-2007 at 12:59 PM.
    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.

  7. #7
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,415
    Not neccesarily. Some compilers can actually optimise recursive functions into iterative loops, or so I hear.
    Tail recursion as in robwhit's example is easy to transform into a loop even for a human, so any optimising compiler should include it.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  8. #8
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046
    [edit] Okay, robwhit just deleted a rather insulting (sorry) post saying something like "lol, I know it would crash, I wasn't expecting anyone to stick my code into a real program." Hence the remainder of this post. [/edit]

    That's the point. It might not crash. If your compiler can optimise that recursive function into an infinite iterative loop, and you have compiler optimisations enabled, then it will act like an infinite loop, and will never segfault or whatever.

    Besides, it depends on your definition of crash. With large percentage of my programs, an infinite loop would be considered a crash.

    [edit]
    Last edited by robwhit : Today at 01:05 PM. Reason: dwks -
    That's pretty funny . . . [/edit]
    Last edited by dwks; 08-21-2007 at 01:08 PM.
    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.

  9. #9
    Registered User
    Join Date
    Oct 2001
    Posts
    2,129
    Quote Originally Posted by dwks View Post
    [edit] Okay, robwhit just deleted a rather insulting (sorry) post saying something like "lol, I know it would crash, I wasn't expecting anyone to stick my code into a real program." Hence the remainder of this post. [/edit]
    what? no I didn't.

    in fact I think it's good that you corrected me. I'd rather people correct me on little things especially, so I don't trip up on them later.

  10. #10
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046
    what? no I didn't.
    Someone did -- I didn't see who -- and from the way it was written I assumed it was the original author of the post in question. That is, you. I must have been mistaken. My apologies.
    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.

  11. #11
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    Recursion really isn't a loop. You could say, any loop is a subset of recursion. Any loop of the form...
    Code:
    loop(N) {
       for (i = 0; i < N; ++i) {
          fn(i);
       }
    }
    Could be expressed recursively as

    Code:
    recurse(N) {
       recurse(N - 1);
       fn(N);
    }

    To really get into what recursion entails sort of involves some CS theory, but a good working definition is "A Recursive Function is Defined in Terms of Itself". A recursive function is very analogous to a mathematical proof that uses induction.


    A friend and I were messing around with server code for an open source game, long ago. The code which caused an enemy to 'aggro' one of the players was killing it (the game was quite fast otherwise). Our solution was thus:

    How to check an area for aggro...
    • Split the map into four quadrants.
    • For each quadrant without players, ignore it.
    • For each quadrant with players, check that quadrant for aggro.


    Code:
    // aggro_mobs(area) is slow when area is large,
    // So split it into smaller areas.
    Check_Aggro (RECT area) {
       if (contains_players(curr_quad) == FALSE)
          // Quad contains no players, abort.
          return;
    
       if (area.x < MIN_RESOLUTION_SIZE) {
          // We've zoomed in closely enough, let the mobs aggro.
          aggro_mobs (area);
          return;
       }
    
       // Area is too big, but not empty.  Break it down.
       Check_Aggro (NORTHWEST_QUAD(curr_quad));
       Check_Aggro (SOUTHWEST_QUAD(curr_quad));
       Check_Aggro (NORTHEAST_QUAD(curr_quad));
       Check_Aggro (SOUTHEAST_QUAD(curr_quad));
    }
    This could fundamentally not be done only using a loop.
    Callou collei we'll code the way
    Of prime numbers and pings!

  12. #12
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,590
    @QuestionC:
    Essentially a type of quad tree test. It would be very hard and awkard to implement a quad-tree without using recursion.


    The cost of the function call and the stack is minimal so long as you don't recurse too far before returning which will cause a stack overflow. I would not bang my head against a wall trying to implement a recursive function iteratively rather than recursively unless the recursive version will cause a stack overflow.

    Writing a floodfill algorithm is one such case. The recursive floodfill works but it will certainly overflow the stack at some point. This almost has to be implemented iteratively which is quite ugly and awkward.

    So it doesn't come down to a simple right way or wrong way but the best way for the problem at hand.

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, 08:45 PM
  2. Recursion... why?
    By swgh in forum C++ Programming
    Replies: 4
    Last Post: 06-09-2008, 09:37 AM
  3. a simple recursion question
    By tetra in forum C++ Programming
    Replies: 6
    Last Post: 10-27-2002, 09:56 AM
  4. To Recur(sion) or to Iterate?That is the question
    By jasrajva in forum C Programming
    Replies: 4
    Last Post: 11-07-2001, 08: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, 01:29 PM

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