# Iteration & Recursion

Iteration and recursion are key Computer Science techniques used in creating algorithms and developing software.

In simple terms, an *iterative* function is one that loops to repeat some part of the code, and a *recursive* function is one that calls itself again to repeat the code. Using a simple *for* loop to display the numbers from one to ten is an *iterative* process. Examples of *simple* recursive processes aren't easy to find, but creating a school timetable by rearranging the lessons, or solving the *Eight Queens Problem* are common examples. I've also created a recursive *Scratch* program to draw binary trees.

*Iteration* and *recursion* are probably best explained using an example of something that can be done using either technique.

## Example

Imagine you wanted to calculate the factorial of an integer (i.e. a whole number) *n* (written n!). To calculate a factorial, we take the number, *n*, and multiply it by all of the integers between 1 and n. So, 2!, for example, is 2 x 1 =
2, 3! = 3 x 2 x 1 = 6, etc. How would you calculate this using a program?

The most obvious way for most people would be to use an *iterative* method - that is, to loop through all the integers from 1 to *n*, multiplying as we go along. Certainly, that would work, and here is the code you could use to do it:

## JavaScript:function factorial(n) { var loop, answer; answer = 1; for(loop=1;loop<=n;loop++) { answer = answer * loop; } return answer; } |

## VBScript:Function factorial(n) dim loop, answer answer = 1 for loop = 1 to n answer = answer * loop next factorial = answer End Function |

Now, that works perfectly, as you can see using the script I've implemented further down the page. A neater and more elegant solution, however, would be to use a *recursive* method.

For every factorial other than 0! (which is 1), we can see that *n! = n x (n - 1)!*, i.e. each factorial is the product of itself and the preceding one, so that 2! = 2 x 1!, 3! = 3 x 2!, 4! = 4 x 3!, etc.

That's really a much simpler idea than looping through all the number from 1 to *n* to calculate the answer, and we can use this method in our program:

## JavaScript:function factorial(n) { if (n == 0) { return 1; } else { return n * factorial(n - 1); } } |

## VBScript:Function factorial(n) if n = 0 then factorial = 1 else factorial = n * factorial(n - 1) End if End Function |

As you can see, the *recursive* approach is not only easier to follow, but requires fewer lines of code, and no variables, rather than the two that the *iterative* method uses.

## Try it out!

The above scripts (the JavaScript version) are included in this page, so you can actually see whether it works (although Netscape appears not to support recursion!):

## Problems

So, which method is best? Well, obviously it depends on what you're trying to do - not all processes will provide an obvious recursive solution. Where they exist, recursive solutions tend to be more elegant, but can potentially be more difficult to understand (an important point to bear in mind if other people are going to be maintaining your code).

Recursive functions may also be executed more slowly (depending on your environment). Each time a function is called, certain values are placed onto the stack - this not only takes time, but can eat away at your resources if your function calls itself many times. In extreme examples you could run out of stack space. Functions that just iterate make no such demands on stack space, and may be more efficient where memory is limited.