Thread: What is the difference between Recursion and Iteration?

  1. #1
    Registered User
    Join Date
    Aug 2006
    Posts
    30

    What is the difference between Recursion and Iteration?

    Can anybody here, discuss to me about recursion and iteration? What are the differences between the two? Thanks...

  2. #2
    Devil's Advocate SlyMaelstrom's Avatar
    Join Date
    May 2004
    Location
    Out of scope
    Posts
    4,079
    Quote Originally Posted by neo_phyte
    Can anybody here, discuss to me about recursion and iteration? What are the differences between the two? Thanks...
    Almost everything... a recursive function works through the process of calling itself until a condition is met. Iteration uses a looping control structure (while, do while, for) to repeat a section of code until a condition is met. All of this is in the tutorials. Recursion is often scary to new programmers, but as you get better it can usually appear as the more logical solution.
    Sent from my iPadŽ

  3. #3
    Registered User
    Join Date
    Aug 2006
    Posts
    30
    thanks...

  4. #4
    Registered User
    Join Date
    Mar 2006
    Posts
    725
    Recursion: See my previous remark about "recursion". For more information you can also check out "recursion".

    Iteration: After reading this word aloud, in between counting from 0 to 1000, you should be able to understand what this means.
    Code:
    #include <stdio.h>
    
    void J(char*a){int f,i=0,c='1';for(;a[i]!='0';++i)if(i==81){
    puts(a);return;}for(;c<='9';++c){for(f=0;f<9;++f)if(a[i-i%27+i%9
    /3*3+f/3*9+f%3]==c||a[i%9+f*9]==c||a[i-i%9+f]==c)goto e;a[i]=c;J(a);a[i]
    ='0';e:;}}int main(int c,char**v){int t=0;if(c>1){for(;v[1][
    t];++t);if(t==81){J(v[1]);return 0;}}puts("sudoku [0-9]{81}");return 1;}

  5. #5
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Quote Originally Posted by neo_phyte
    Can anybody here, discuss to me about recursion and iteration? What are the differences between the two? Thanks...
    IMO, there's very little difference between recursion and iteration. Anything done in one style of looping, can be done in the other.

    Algorithms which use some type of "divide and conquer" method, do very well with recursion. Quicksort is a great example.

    So why is binary search (which also uses "divide and conquer" methodology, not usually done using recursion?

    Because binary search needs no other "bookmarks" to "keep it's place", as it searches through an array (or whatever). Since everything being looked through is already sorted, the low and high variables in the binary search, give just about everything you need to smartly keep your place within the search space.

    Contrast that with Quicksort, where you have all these little sub-divisions, each with a different size possibly, (and that size changing all the time), and you can see it's a bookkeeping nightmare to do it in an iterative style.

    In the recursive style, Quicksort's needs are addressed nicely by the internal stack for each successive call to the function. It's a bit like magic the way the stack keeps track of this stuff. One author described recursion as "like you called the painters to paint your room, and hung up the phone and "poof!", the room was already painted!"

    So imo, recursion is best when you have a lot of variables to keep track of with each loop, and it's using a "divide and conquer" type of algorithm. Recursion helps to trim down the frame of reference (the portion of the problem you're now interested in), very easily.

    When you have few variables to keep track of, or the algorithm isn't some type of "divide and conquer", then I find iterative looping, more to the point.

    Iteration is slightly faster, but that should not be the criteria used to choose it. The difference is very small, and the clarity and shortness of the recursive code, can be quite helpful.

    I've used Quicksort in an iterative style - and it is just UGLY.

    Adak

  6. #6
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    IMO, there's very little difference between recursion and iteration.
    Well strangely your stack does not agree.

  7. #7
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    K&R-2 sums up recursion quite nicely - just try looking it up in the index
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  8. #8
    aoeuhtns
    Join Date
    Jul 2005
    Posts
    581
    Ultimately, iteration is just a convenient (inconvenient?) way of writing a recursive definition of an algorithm. For example,
    Code:
    int fac_times(int p, int n) {
      if (n == 0)
        return p;
      return fac_times(p * n, n - 1);
    }
    Code:
    int fac_times(int p, int n) {
      while (n != 0) {
        p = p * n;
        n = n - 1;
      }
      return p;
    }
    Here, one is implemented recursively, one is implemented with a while loop. But note that the recursive call is in effect nothing more than a jump to the top, with new values for n and p. The same goes for the while loop. The only difference between them is that one might get compiled differently from the other (with the recursive solution being more likely to be compiled inefficient/bad). It's usually better to think about iteration as a recursive process.
    There are 10 types of people in this world, those who cringed when reading the beginning of this sentence and those who salivated to how superior they are for understanding something as simple as binary.

  9. #9
    Jaguar
    Join Date
    Sep 2006
    Posts
    12
    But recursion needs a bigger stack since it has to go back.
    So try to avoid recursion wherever possible.

    Jag

  10. #10
    Registered User
    Join Date
    Mar 2006
    Posts
    725
    Not all recursion it to be avoided. Iterative code can be larger and slower, and cause more cache misses and pipelining issues. This is typical of an iterative implementation of branching algorithms, like Quicksort.

    Algorithmically, iteration and recursion are two roads to the same Rome.


    By the way, the Halting Problem was first solved using recursive models (Church), not iterative ones (Turing)
    Code:
    #include <stdio.h>
    
    void J(char*a){int f,i=0,c='1';for(;a[i]!='0';++i)if(i==81){
    puts(a);return;}for(;c<='9';++c){for(f=0;f<9;++f)if(a[i-i%27+i%9
    /3*3+f/3*9+f%3]==c||a[i%9+f*9]==c||a[i-i%9+f]==c)goto e;a[i]=c;J(a);a[i]
    ='0';e:;}}int main(int c,char**v){int t=0;if(c>1){for(;v[1][
    t];++t);if(t==81){J(v[1]);return 0;}}puts("sudoku [0-9]{81}");return 1;}

  11. #11
    Registered User
    Join Date
    Aug 2006
    Posts
    30
    thanks to all you guys for the helpful information...

  12. #12
    Registered User Micko's Avatar
    Join Date
    Nov 2003
    Posts
    715
    Here's one more thing you can read
    Gotta love the "please fix this for me, but I'm not going to tell you which functions we're allowed to use" posts.
    It's like teaching people to walk by first breaking their legs - muppet teachers! - Salem

  13. #13
    Registered Luser risby's Avatar
    Join Date
    Jun 2006
    Posts
    72
    Until you understand recursion go here
    ===
    Don't grumble about what you can't have;
    be grateful you don't get what you deserve.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. iteration and recursion question
    By Stonehambey in forum C++ Programming
    Replies: 3
    Last Post: 03-19-2008, 06:16 PM
  2. Recursive function crashes.
    By samus250 in forum C Programming
    Replies: 9
    Last Post: 01-16-2008, 02:58 PM
  3. Recursion vs. Iteration
    By simpleid in forum C++ Programming
    Replies: 5
    Last Post: 06-06-2007, 01:17 PM
  4. Iteration and recursion?
    By Munkey01 in forum C++ Programming
    Replies: 15
    Last Post: 01-18-2003, 08:16 PM
  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