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.