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!):


Enter a value:

factorial is

Calculate using:

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.