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 and lattices.

Iteration and recursion are probably best explained using an example of something that can be done using either technique.  If you want visual analogies of recursion, I'm compiling some examples here.

Examples

The difficulty, when teaching or learning about recursion, is finding examples that students recognise, but which are also worthwhile uses of recursion.  Here are three common examples.  If you'd rather watch a video, you can watch me explain these three recursive functions in Python.

Factorials

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!):  You can also see Python versions of the iterative and recursive versions on my Repl.it page.


Enter a value:

factorial is

Calculate using:

Palindromes

A palindrome is a word that is the same when reversed, e.g. madam.  The string can be reversed using an iterative method, or string-slicing in Python, but there is also a recursive method.

A word is a palindrome if it has fewer than two letters, or if the first and last letter are the same and the middle part (i.e. without the first and last letters) is a palidrome.  You can see the Python code for this method in Repl.it.

Prime Factorisation

A factor of a number is a value that divides exactly into that value, e.g. the factors of 12 are 1, 2, 3, 4, 6 and 12.  A prime number is a number with only two factors - one, and itself.  A prime factor is just a factor that is a prime number, and any integer greater than one can be split into prime factors, e.g. 12 is 2 x 2 x 3.  Finding the prime factors of very large numbers is a technique used in encryption.

A manual technique often involves drawing a factor tree, splitting a number into two factors, and then further splitting each of the factors into its factors.  The recursive algorithm is essentially the same - we can loop through possible factors and use modular arithmetic to determine whether they are indeed a factor.  When we find a factor, we call the function again on that factor and it's pair (i.e. the original number divided by the factor we've just found).  See an implementation of this method in Python on my Repl.it page.

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.