Recursion and Iteration
(Up to Basic Computer Science)

Recursion and iteration are two very commonly used, powerful methods of solving complex problems, directly harnessing the power of the computer to calculate things very quickly. Both methods rely on breaking up the complex problems into smaller, simpler steps that can be solved easily, but the two methods are subtlely different.

Iteration, perhaps, is the simpler of the two. In iteration, a problem is converted into a train of steps that are finished one at a time, one after another. For instance, if you want to add up all the whole numbers less than 5, you would start with 1 (in the 1st step), then (in step 2) add 2, then (step 3) add 3, and so on. In each step, you add another number (which is the same number as the number of the step you are on). This is called "iterating through the problem." The only part that really changes from step to step is the number of the step, since you can figure out all the other information (like the number you need to add) from that step number. This is the key to iteration: using the step number to find all of your other information. The classic example of iteration in languages like BASIC or C++, of course, is the for loop.

If iteration is a bunch of steps leading to a solution, recursion is like piling all of those steps on top of each other and then quashing them all into the solution. Recursion is like holding a mirror up to another mirror: in each image, there is another, smaller image that's basically the same.

This is best explained with an example. How would you tell a computer to see if someone is a descendant of Ghengis Khan? Perhaps the algorithm to define who is and isn't a descendant of Ghengis Khan would look like this:

The person is an heir to Ghengis Khan if his/her father is named Ghengis Khan, or his/her father or mother is an heir to Ghengis Khan.

Wait, haven't we violated a basic rule that we learned in elementary school - not to use word (in this case, phrase) in its own definition? Well, we aren't exactly using circular logic here, since we aren't saying "an heir to Ghengis Khan is an heir to Ghengis Khan." Let's trace this definition out a bit:

Take Jim. He doesn't know it, but he's the direct great-grandson of Ghengis Khan, through a series of male heirs. Since Jim's father isn't named Ghengis Khan, we have to see if his father is an heir...so, we just try the definition again on his father, just like we did with Jim. Jim's father's father (his grandfather) isn't named Ghengis Khan, so we have to look at Jim's father's father's father (his great-grandfather). But wait! His great-grandfather is named Ghengis Khan. So, this means that Jim's grandfather is an heir, which means that his father is an heir, which means that Jim is an heir.

If you notice, we went deeper and deeper into the problem, using the same method over and over until we reached something that was new, an "endpoint". After this, we sort of "unwound" the problem until we arrived where we began, except with the problem solved. This kind of "self-cloning" technique of recursion leads to a famous programmer's joke:

So, the difference between iteration and recursion is that with iteration, each step clearly leads onto the next, like stepping stones across a river, while in recursion, each step replicates itself at a smaller scale, so that all of them combined together eventually solve the problem. These two basic methods are very important to understand fully, since they appear in almost every computer algorithm ever made.