Originally published by Robert Beisert at fortcollinsprogram.robert-beisert.com

CS 101 – Recursion and Iteration

Many problems in this world require us to perform a series of steps over and over, looking for the correct result. In computer programming, we have three ways to do this.

Keep it Simple

Of course, if you really want to make this easy for yourself, you just write the solution as one big block. This is a nasty way to program, because you spend more time with copy-paste than you spend on actual programming.

More importantly, many problems require us to repeat a small block of code a variable number of times. There is just no good way to write this in a block format.

Iteration

Iteration is a fancy word for repetition. When we iterate over a piece of code, we repeat it until a certain condition is met.

A common way to iterate is to employ the for loop. Recall that the format for for is:

for (initial condition; test; iteration)

The single most common use of for follows the following format:

for( int i = 0; i < 10; i++)

This is an iterative loop which starts at 0 and counts up to 9. BEWARE THE OFF-BY-ONE ERROR, which is very common when starting out programming. Running this iteration looks something like this:

1st time: 0

2nd time: 1

3rd time: 2

4th time: 3

5th time: 4

6th time: 5

7th time: 6

8th time: 7

9th time: 8

10th time: 9

So we see that it runs 10 times, but the value for i never goes higher than 9.

Recursion

Sometimes we have absolutely no idea how many times we’ll have to repeat the problem before we get the right answer.

Imagine you have a very long list with over 500 items in it. You want to write a program to give you the item labelled “catfish nuggets”, but you have no idea where it is in the list. Using iteration, you could try something like this:

for(int i=0; i < 500; i++)

if ( item i in LIST is “catfish nuggets”)

print item i in LIST

This is a very effective solution to the problem. However, there is another option.

Recursion is another word for repetition. When we use recursion, we run the same algorithm over a smaller set of the problem. In this example, we can use recursion to find “catfish nuggets” by making LIST smaller each time.

FUNCTION FIND_FISH (LIST):

if (first item in LIST is not “catfish nuggets”)

FIND_FISH(LIST without first item)

else if(LIST is empty)

print “Nothing here, cap’n”

else

print “Found catfish nuggets”

Admittedly, if I had this particular problem, I would probably use iteration, but there are excellent times to use recursion. Practice writing recursion on easy problems so you know how to do it for the harder ones.