When to use recursion?

This is a discussion on When to use recursion? within the C Programming forums, part of the General Programming Boards category; I keep coming across problems that are solved using recursion, when they could be solved more easily using iteration. Can ...

  1. #1
    Unregistered
    Guest

    When to use recursion?

    I keep coming across problems that are solved using recursion, when they could be solved more easily using iteration. Can you give me an example of a problem that is much easier to solve using recursion?

  2. #2
    ....
    Join Date
    Aug 2001
    Location
    Groningen (NL)
    Posts
    2,386
    Iteration is more effective than recursion. But a recursive algorithm is sometimes better to understand, especially when a (mathematical) function is recursive. Like Fibonacci-series, series in general, faculty function, algorithms on trees etc.

  3. #3
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    I keep coming across problems that are solved using recursion, when they could be solved more easily using iteration.
    Maze generation. You can use a loop, but it's generally much easier to just use recursion to do it for you:

    Code:
    Move( here )
    {
        while( one_or_more_unused_neighbors( here ) )
            direction = get_random_unused_neighbor( here )
            set_used( direction )
            move( direction )
    
        return
    }
    See, basicly what you do is this: If there is no way to go, then you've reached a dead end, so backtrack (return), otherwise, pick an unused direction and move there. Eventually, you'll end up with every cell in the maze linked by a single path.

    It can be done with looping and no recursion, but it pretty much sucks that way.


    Quzah.
    Hope is the first step on the road to disappointment.

  4. #4
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    Here are two ways to determine how many ways there
    are to count a certain amount of change with pennies,
    nickles, etc.

    With recursion
    Code:
    int count_change(int amount)
    {
        return cc(amount, 4);
    }
    
    int cc(int amount, int coin)
    {
        static const int denom[] = {1, 5, 10, 25, 50};
    
        if (amount == 0) 
            return 1;
        else if (coin < 0 || amount < 0) 
            return 0;
        return cc(amount - denom[coin], coin) + cc(amount, coin - 1);
    }
    Without recursion
    Code:
    int count_change(int amount)
    {
        int i, j, k, m, n;
    
        int c = 0;
        for (i = amount; i > 0; i -= 50) {
            for (j = i; j > 0; j -= 25) {
                for (k = j; k > 0; k -= 10) {
                    for (m = k; m > 0; m -= 5) {
                        for (n = m; n > 0; n--) 
                            ;
                        if (n == 0) 
                            ++c;
                    }
                    if (m == 0) 
                        ++c;
                }
                if (k == 0) 
                    ++c;
            }
            if (j == 0) 
                ++c;
        }
        if (i == 0) 
            ++c;
        return c;
    }

  5. #5
    Registered User
    Join Date
    Aug 2001
    Posts
    202
    The beauty of recursion is that it tends to allow you to not have to plan for every single possible scenario in a complex program. This comes a great deal into play with various searching and sorting algorithms, as well as data structures like binary trees.

    The simple fact is that the recursion tends to do the work for you when pro[perly implimented, and while this doesn't matter so much with simple programs, I think you'll find that in more complex scenarios, iterators get more complicated than they're worth.

    Besides, as my CS prof always used to say: "To iterate is human, to recurse is devine."

    starX
    www.axisoftime.com

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. convert Recursion to linear can it be done
    By umen242 in forum C++ Programming
    Replies: 2
    Last Post: 10-15-2008, 03:58 AM
  3. Recursion... why?
    By swgh in forum C++ Programming
    Replies: 4
    Last Post: 06-09-2008, 10:37 AM
  4. a simple recursion question
    By tetra in forum C++ Programming
    Replies: 6
    Last Post: 10-27-2002, 10:56 AM
  5. 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

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