Rad wrote on Aug 16th, 2009 at 4:59pm:Can you explain the differnces between recursive & iterative? (in a nutshell)
I'll try.
In both, you are breaking a problem into smaller sub-problems and then solving the sub-problems. The difference is that in iteration, you have an answer for each sub-problem before moving onto the next sub-problem. With recursion, each sub-problem depends on the answer from the next sub-problem, so all the sub-problems wait until the last sub-problem is solved before they can each finish.
There might be a more formal and complete definition somewhere, but that's off the of my head. It's easiest to see if you look at an example of code from each, so I'll demonstrate with some sudo-code (not syntatically correct for any particular language) to find factorial numbers:
4! = 4 * 3 * 2 * 1
5! = 5 * 4 ...
0! = 1 (this is by definition)
so the iterative solution would be something like:
sub factorial ( inputNum ) {
answer = 1
for loopCount = 1 to inputNum {
answer = answer * loopCount
}
return answer
}
Basically this initializes the answer at 1, loops from 1 to the input number, multiplying the answer by the number of the loop we are on each time. (This particular implementation wouldn't work for negative factorials, but its just to demonstrate an iterative procedure.)
The recursive solution would be something like:
sub factorial ( inputNum ) {
if inputNum = 0 then return 1
else return inputNum * factorial( inputNum - 1 )
}
So, if the input number is 0, this version immediately returns 1. If the input number is not 0, we return the input number multiplied by the factorial of the input number - 1. The second factorial function call goes through a similar check to see if the input number is 0. If not, the process repeats until the input number becomes 0.
At that point, 1 is returned. That allows the next to last call to return 1 * 1, which allows the second to last call to return 2 *1, which allows the third to last call to return 3 * 2, etc until all calls to factorial have returned and we have the correct answer.
Recursion can be a very expressive way to solve problems, but it has some dangers. For example, we saw that the iterative version doesn't find the correct answer for negative numbers. The recursive version, on the other hand, won't ever return an answer at all. If given a negative number, it will enter an infinite loop and, if left running long enough, will take up all available memory and crash the machine it is running on.
The book Higher Order Perl has a great discussion of recursion. An old version (although still perfectly relevant) is available online:
http://hop.perl.plover.com/I've actually read (although not necessarily fully comprehended) most of that book. I learned so much from it that I bought the dead tree version.