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...

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.

thanks...

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.

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

Quote:

---

IMO, there's very little difference between recursion and iteration.

---

Well strangely your stack does not agree.

K&R-2 sums up recursion quite nicely - just try looking it up in the index ;)

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.

But recursion needs a bigger stack since it has to go back.
So try to avoid recursion wherever possible.

Jag

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

thanks to all you guys for the helpful information...

Here's one more thing you can read

Until you understand recursion go here