When to use recursion?

[Unregistered]

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?

[Shiro]

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.

[quzah]

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:

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.

[Nick]

Here are two ways to determine how many ways there
are to count a certain amount of change with pennies,
nickles, etc.

With recursion

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

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;
}

[starX]

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