Is recursion truly superior to iteration?

[dashkin111]

When is recursion really better than iteration. I'm not a programmer by major, but I can't think of any time when recursion would be better

 

[las3rjock]

There are many divide-and-conquer algorithms that are much easier to implement by recursion than by iteration. Examples that come to mind are quicksort, the fast Fourier transform, and the fast multipole method. Unfortunately, the most common example used to illustrate recursion is the factorial function, which is better implemented by iteration.

 

[D H]

Try writing a program to compute the Ackermann function in a non-recursive language. I still remember that exercise twenty some years. Doing this in Fortran and assembly was painful. In a recursive language it takes but a few lines of code. The Ackermann function is

Edit: I give up. Sometimes the limited LaTeX here bites.
A(m,n) = n+1 if m=0,
A(m,n) = A(m-1,1) if n=0,
A(m,n) = A(m-1,A(m,n-1)) otherwise.

 

[rcgldr]

There are cases where the nature of the programming is recursive. One example is an expression evaluator that allows parenthesis (like a calculator). It's easier to use just make a recursive call for each "(" encountered, and to return with a value for each ")" encountered in such a case, but otherwise just iterate for all the mathematical operators like + - x / (assuming no precedence here).

Another example is a program that follows a directory tree, especially if the program processes all files within a directory before processing sub-directories. I think of this as a program that makes uses recursion to create a "new instance" of a program state, with the ability to return to a "previous instance".

I use the following logic as the basis of a file copy program to backup / restore / defrag partitions on my system. The issue in this sample code is that there are two loops and the second loop needs to be able to "call" a new instance of both loops, then "return" back to a previous instance of the second loop.

ProcessDirectory(...)
{

    ForEachFile()
    {
        ProcessFile();
    }

    ForEachDirectotry()
    {
        ProcessDirectory()
    }
}

ProcessFile(...)
{

}

 

[D H]

Excellent example, Jeff. Tree traversal is a bear in a non-recursive language. You essentially have to reinvent all of the machinery you get for free with recursion to do tree traversal iteratively.

 

[-Job-]

Also for enumerating all subsets and permutations of an input set of n elements for example.

 

[dashkin111]

Thanks everyone, this is helpful to me.