Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Recursion vs. Iteration

  1. Oct 8, 2007 #1
    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
     
  2. jcsd
  3. Oct 8, 2007 #2
    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.
     
  4. Oct 8, 2007 #3

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    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.
     
    Last edited: Oct 8, 2007
  5. Oct 8, 2007 #4

    rcgldr

    User Avatar
    Homework Helper

    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.

    Code (Text):

    ProcessDirectory(...)
    {

        ForEachFile()
        {
            ProcessFile();
        }

        ForEachDirectotry()
        {
            ProcessDirectory()
        }
    }

    ProcessFile(...)
    {

    }
     
     
    Last edited: Oct 8, 2007
  6. Oct 8, 2007 #5

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    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.
     
  7. Oct 9, 2007 #6

    -Job-

    User Avatar
    Science Advisor

    Also for enumerating all subsets and permutations of an input set of n elements for example.
     
  8. Oct 9, 2007 #7
    Thanks everyone, this is helpful to me.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Recursion vs. Iteration
  1. Recursion in C (Replies: 12)

Loading...