1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Recursive vs iterative approach

  1. Nov 2, 2012 #1
    Maybe this question better belongs to programming section but I feel it has mathematics related doubt.

    I want an intuition on how iterative and recursive approaches are different. Just look at the simple arithmetic progression. nth term is given as a + n.d. This can be derived using both iterative and recursive methods.
    I am looking for the basic idea behind both the approaches.
    Also can all recursive solution be converted to iterative solution? In Fibonacci sequence can nth term be found iteratively?

    So if all iteraitve and recursive solutions be interconvertible whats the basic difference between both, i mean the basic crux or logic behind both?
    Ah, I still feel I couldn't convey my question!
     
  2. jcsd
  3. Nov 2, 2012 #2
    I can try to answer.

    Basically a recursive algorithm calculates a number then uses the number it just calculated to calculate the next number, and so on. An iterative algorithm is a algorithm which 'calls' itself at some point in it's progression.

    The fibonacci sequence is a really good example of this. You can write functions (I'm assuming you know some basic programming - stop me if I'm off) that calculate terms in the Fibonacci sequence, store those terms as variables, and use that variable to compute the next term; this is a recursive approach.

    You can also write a function which seems to be doing the same thing but instead of storing a number as a variable the function calls itself. Meaning at some line in a int Function() you would have a call to int Function(), a.k.a a call to itself. This creates a nested function within a function that can be evaluated to produce terms in the Fibonacci sequence. This is an iterative approach.

    I have to run or else I would show the code in both these cases. If no one else has answered your question better later I can edit in some stuff.
     
  4. Nov 2, 2012 #3

    rcgldr

    User Avatar
    Homework Helper

    For computer science (programming), an interative approach is one that uses one or more loops within a function, while a recursive approach is one where a function calls itself. Wiki article:

    wiki_recursion_cs.htm

    A recursive approach can be converted into an iterative approach by using an array to replace the functionality of the stack. In some cases, there may be an naturally iterative approach that can be used instead of a recursive approach.

    An iterative approach can be converted into a recursive approach by passing all the loop related variables as parameters to a self called function, but this is usually inefficient.
     
  5. Nov 2, 2012 #4
    My trusty maths dictionary (this is the maths forum, not the programming one) says that they mean the same thing.

     
  6. Nov 2, 2012 #5
    Ah! I apologize, I mixed up the terms. Idiotic on my part, sorry OP.

    My C++ book literally starts the chapter on recursion with "A recursive function in C++ is a function that calls itself."
    Should have checked before I posted.

    Sorry :)
     
  7. Nov 2, 2012 #6

    rcgldr

    User Avatar
    Homework Helper

    In the case of math, the definitions overlap. Wiki articles mentions that recursion repeats in a self-similar way:

    http://en.wikipedia.org/wiki/Iteration

    http://en.wikipedia.org/wiki/Recursion

    For computer science (programming), the terms have different meanings as explained above: iteration means looping, recursion means a function that calls itself.

    Example of converting a recursive approach to an interative approach.

    http://www.guineacode.com/2012/iterative-recursion [Broken]

    Yes, link to example progam:

    http://www.dreamincode.net/code/snippet3181.htm [Broken]
     
    Last edited by a moderator: May 6, 2017
  8. Nov 2, 2012 #7

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    In software, the difference is essentially that they work from opposite ends. In iteration, you start with an almost trivial case and solve it; then using that you can solve the next case. In recursion, you start from the endpoint and reason that you could solve that if you knew the answer to the next simpler case - so you go off and solve that then return to complete the job.
    The advantage of recursion is elegance. Take the towers of Hanoi problem. It's easy to see that a solution is:
    To move the top N discs from tower A to tower B
    - move the top N-1 from tower A to tower C
    - move the top disc from A to B
    - move the top N-1 from C to B
    Once you've observed that is a solution, it's quite easy to restructure it as iteration, but either way it takes 2^N steps.
    Fibonacci, OTOH, demonstrates a serious disadvantage of recursion. The number of steps required is again exponential (equal roughly to the value that will be computed). But the iterative solution only takes N steps.
    Another disadvantage of recursion is stack size, which can be hard to anticipate.

    In theoretical computing and some related fields, recursive definitions arise. E.g. in the definition of a statement in a given computer language. Not sure how you'd replace those with a form of iteration. In consequence, the compiler likely analyses the program recursively, but I couldn't swear to that.

    In mathematical induction, I don't see a distinction. You have the inductive step and the base case, but whether you think of the proof as running backwards to or forwards from the base case is a matter of taste.
    There is a trap using recursion in mathematical definitions. If you attempt to use the definition to assess whether an object satisfies it, you could find yourself in infinite regress. You need some way of ensuring that the recursive analysis terminates for any given object - otherwise the definition is broken.
     
  9. Nov 4, 2012 #8
    I recommend looking at the factorial function. It can both be implemented iteratively and recursively.

    As already mentioned iteration involves using for loops. The recursive approach uses a function that calls itself.
    This sounds a little strange but let's have a look at how 3! is calculated:


    1. iteration:
    Simply calculate 1*2*3
    Code (Text):

    result = 1
    for(i=1 to 3):
         result = result*i

    print result
     

    2. recursion:
    The recursive function is defined as:
    Code (Text):

    f(1)=1  
    f(n) = n*f(n-1)
     
    Plug in n=3:
    f(3) = 3*f(3-1) = 3*f(2)

    What is f(2)?
    f(2) = 2*f(2-1) = 2*f(1)

    What is f(1)?
    f(1) = 1, according to definition

    Let's write everything in succession:
    f(3)
    = 3*f(2)
    = 3*(2*f(1))
    = 3*(2*(1))
     
  10. Nov 5, 2012 #9
    These comments are true if you actually (intend to) carry out all the steps.

    It is often possible, however, to develop a formula for the nth term without this effort.
     
  11. Nov 5, 2012 #10

    AlephZero

    User Avatar
    Science Advisor
    Homework Helper

    That's true for a simple implementation of recursion, but there are ways round it. One improvement is to remember everything you already calculated, so you don't have to calculate it again. For example to calculate the 10th Fibonacci number, you have
    f(10) = f(9) + f(8) ... (*)
    So you start by calculating f(9)
    f(9) = f(8) + f(7), etc

    But after you have done that, you already know the value of f(8) to finish calculating Eq. (*), so you don't need to calculate f(8) again.

    This is a very powerful idea in situations where you can't easily analyze the complete algorithm in advance to figure out what you need to calculate. An example would be a chess program looking at possible future moves, There are often many different ways of getting to the same position on the board, but the "history" of how you got there is irrelevant to how good the position is. (OK, that's a slight simplification of the real rules of chess, to simplfy the example!)
     
  12. Nov 5, 2012 #11

    rcgldr

    User Avatar
    Homework Helper

    Such as an array FIB[] to hold the fibonacci numbers, initialized to zero so that if(FIB[k] != 0) would indicate FIB[k] was previously calculated. Even with this improvement, there's still the additional call and stack overhead versus the iterative method for fibonacci numbers.

    - - -

    Perhaps a better example for using recursion would be navigation of a tree like structure, such as the files and folders in a partition. Assume the goal is to process all files in the current directory first, then to recursively process all sub-directories in the current directory. There are two main loops, one to process files, the other to process sub-directories. Iteration would be awkward since the recursion returns back into the middle of the second loop. The code would look something like this:

    Code (Text):

    typedef _DIR{   // directory structure
    _DIR * pnext;   //  ptr to next entry
    _DIR * psubdir; //  ptr to sub-directory
                    //    or NULL if file
    // ...          //  directory entry data
    }DIR;

    void ProcessFile(DIR * pdir); // ...

    void ProcessDirectory(DIR * pdir)
    {
    DIR *pent; // used to scan entries in pdir

        pent = pdir;
        while(pent){
            if(pent->psubdir == NULL) // if file
                ProcessFile(pent);
            pent = pent->next;
        }

        pent = pdir;
        while(pent){
            if(pent->psubdir != NULL) // if sub-dir
                ProcessDirectory(pent->psubdir);
            pent = pent->next;
        }
        return;
    }
     
     
    Last edited: Nov 6, 2012
  13. Nov 6, 2012 #12
    You can use recurrence relations for recursion.
     
  14. Nov 6, 2012 #13
    Why is recursion sometimes easier that iteration. Programs like n-queens and knights tour are easy using recursion but I struggle making them using iteration.

    So what advantage does recursion offer in such cases. Why its easier to think recursive in some cases?
     
  15. Nov 6, 2012 #14

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    That depends on how you code the recursive solution. The naive implementation is exponential. The following recursive implementation only takes N recursive calls, and since it's a tail recursive algorithm, most compilers will optimize away the recursion. In C++,
    Code (Text):
    #include <iostream>
    #include <stdint.h>

    uint64_t fibonacci_helper (uint64_t N, uint64_t prev, uint64_t curr)
    {
       return (N == 0) ? curr :  fibonacci_helper (N-1, curr, prev+curr);
    }

    uint64_t fibonacci (uint64_t N)
    {
       return (N == 0) ? 0 : fibonacci_helper (N-1, 0, 1);
    }

    int main ()
    {
       std::cout << "Fib(20) = " << fibonacci(20) << "\n";
       std::cout << "Fib(93) = " << fibonacci(93) << "\n";
       return 0;
    }
     

    With C++ you can also use templates to get an O(1) runtime solution:
    Code (Text):
    #include <iostream>
    #include <stdint.h>

    template<uint64_t N>
    struct template_fibonacci {
       enum {
          value = template_fibonacci<N-2>::value + template_fibonacci<N-1>::value
       };
    };

    template<> struct template_fibonacci<0> { enum { value = 0ull }; };
    template<> struct template_fibonacci<1> { enum { value = 1ull }; };

    int main ()
    {
       std::cout << "Fib(20) = " << template_fibonacci<20>::value << "\n";
       std::cout << "Fib(93) = " << template_fibonacci<93>::value << "\n";
       return 0;
    }
    Note that this uses the simple version of the recursive Fibonacci algorithm. The upside is that the compiler automagically does the memoization (what AlephZero wrote about in post #10). The downside is that you can't compute template_fibonacci<N>::value where N is a runtime integer.
     
    Last edited: Nov 6, 2012
  16. Nov 6, 2012 #15

    rcgldr

    User Avatar
    Homework Helper

    Code (Text):
    #include <iostream>
    #include <stdint.h>

    uint64_t fibonacci_helper (uint64_t N, uint64_t prev, uint64_t curr)
    {
       return (N == 0) ? curr :  fibonacci_helper (N-1, curr, prev+curr);
    }

    uint64_t fibonacci (uint64_t N)
    {
       return (N == 0) ? 0 : fibonacci_helper (N-1, 0, 1);
    }
     
    This seems very similar to An iterative approach can be converted into a recursive approach by passing all the loop related variables as parameters to a self called function ... , where recursion is just being used as a loop mechanism, and the stack is filled with instances of the iterated values. fibonacci() and fibonacci_helper() could be translated into this iterative code:

    Code (Text):


        if(N == 0)       // fibonacci()
            return(0);
        prev = 0;
        curr = 1;
        N = N - 1;

        while(N != 0){  // fibonacci_helper()
            sum = curr + prev;
            prev = curr;
            curr = sum;
            N = N - 1;
        }
     
     
    Last edited: Nov 7, 2012
  17. Nov 7, 2012 #16

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    I like to look at it the other way around: That a tail recursive algorithm can be converted to an iterative algorithm. That's what a good optimizing compiler for C or C++ is going to do. However, C and C++ are not the only languages in the world. In a functional language such as Lisp or Haskell, the underneath the hood implementation of an iterative algorithm is to convert it to a recursive one.

    Here's one more recursive implementation of the Fibonacci algorithm. Note this is not tail recursive.
    Code (Text):
    uint64_t fibonacci (
       uint64_t N)
    {
       if (N == 0) {
          return 0;
       }  
       else if (N == 1) {
          return 1;
       }  
       else {
          uint64_t k = N >> 1;
          uint64_t f1 = fibonacci(k);
          uint64_t f2 = fibonacci(k-1);

          if ((N & 1ull) == 0ull) {
             return f1 * (f1 + f2 + f2);
          }  
          else if ((N & 3ull) == 1ull) {
             return (f1 + f1 + f2) * (f1 + f1 - f2) + 2ull;
          }  
          else {
             return (f1 + f1 + f2) * (f1 + f1 - f2) - 2ull;
          }  
       }  
    }
    The above is an O(N) algorithm, same as the tail recursive version. Add memoization to the above and you get an O(log(N)) algorithm.
     
  18. Nov 7, 2012 #17

    rcgldr

    User Avatar
    Homework Helper

    OK. My issue was that all the iterated variables (prev, curr, prev+curr) were being passed as parameters, so it didn't seem that recursion was accomplishing much with that implementation of fibonacci, plus it added the overhead of pushing all instances of those iterated vairable onto the stack (assuming a compiler didn't convert it to an iterative algorithm).

    This one is better although a bit more complex, although again it seems a similar approach could be done iteratively.

    I think the directory / nodal tree scan example from my earlier post is a better case for using recursion than fibonacci. Fibonacci can be easily implemented iteratively, but the two loop (1st loop for files / leaves, 2nd loop for sub-directories / sub-nodes) directory / tree scan, is awkward to implement iteratively, depending on the language (in C, it requires a goto to jump into the middle of the 2nd loop when the end of the current directory / branch is reached, in addition to restoring pointers / variables to the next "higher" directory / node).
     
    Last edited: Nov 7, 2012
  19. Nov 7, 2012 #18
    As I asked earlier, why is recursion sometimes much easier to implement than iteration even though it seems like both methods are almost the same?
     
  20. Nov 8, 2012 #19

    rcgldr

    User Avatar
    Homework Helper

    It mostly depends if the algorithm you've choosen is more oriented to an iterative or recursive implementation. The directory / tree scan algorithm example I mentioned earlier is more oriented to a recursive implementation because the nature of the structure of the directory / tree is recursive. Fibonacci or any summation or product series can be implemented either way, but usually an iterative approach will be more efficient. A merge sort can be implemented bottom up using iteration, or top down using recursion, but the bottom up iterative approach is more efficient. If you're not familiar with merge sort, wiki article:

    http://en.wikipedia.org/wiki/Merge_sort
     
    Last edited: Nov 8, 2012
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Recursive vs iterative approach
  1. Iterated integrals (Replies: 6)

  2. Iterated tangent (Replies: 0)

  3. Iterative routines (Replies: 13)

  4. Simple recursion (Replies: 3)

Loading...