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

Printable View

- 09-11-2006neo_phyteWhat 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...

- 09-11-2006SlyMaelstromQuote:

Originally Posted by**neo_phyte**

- 09-11-2006neo_phyte
thanks...

- 09-11-2006jafet
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. - 09-11-2006AdakQuote:

Originally Posted by**neo_phyte**

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 - 09-11-2006VirtualAceQuote:

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

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

- 09-11-2006Rashakil Fol
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;

}

- 09-11-2006jaguar23
But recursion needs a bigger stack since it has to go back.

So try to avoid recursion wherever possible.

Jag - 09-12-2006jafet
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) ;) - 09-12-2006neo_phyte
thanks to all you guys for the helpful information...

- 09-13-2006Micko
Here's one more thing you can read

- 09-13-2006risby
Until you understand recursion go here