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 Sudoku or 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 - or have a look at the animation at the foot of the page.

Examples

The difficulty, when teaching or learning about recursion, is finding examples that students recognise, but which are also worthwhile uses of recursion.  There are some examples of recursions on my Python examples page.  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:

function factorial(n)
{
   var loop, answer;
   answer = 1;

   for(loop=1;loop<=n;loop++)
   {

      answer = answer * loop;		

   }

   return answer;
}

Function factorial(n)

   dim loop, answer
   answer = 1

   for loop = 1 to n

    answer = answer * loop		

   next

   factorial = answer

End Function

def factorial(n)

   answer = 1

   for loop in range(1, n+1):

      answer *= loop		

   return answer

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:

function factorial(n)
{

   if (n == 0) 
   { 

      return 1;

   }
   else 
   {

      return n * factorial(n - 1);

   }

}

Function factorial(n)

   if n = 0 then 

      factorial = 1

   else 

      factorial = n * factorial(n - 1)

   End if

End Function

def factorial(n)

   if n == 0: 

      return 1

   else 

      return n * factorial(n - 1)

      

      

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 replit.com page.

Highest Common Factor

Whilst thinking about programming tasks for GCSE students, I came across this video on calculating the Highest Common Factor (HCF of two numbers). There is actually a better explanation of the process in the commments.

The HCF of two numbers is the same of the HCF of one of the numbers and the difference between them. If you use the smaller number and repeat the process you end up with the number numbers being the same, in which case that is the HCF. See this recursive HCF function in Python.

Flood Fill

In some ways this is the ideal starting point for developing an understanding of recursion because flood-fill is a simple idea to understand, and also uses a recursive procedure, rather than a function, so there are no tricky return values to worry about. The explanation of flood fill has its own page.

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 replit.com.

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 replit.com 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.

Finally... Recursive Backtracking

There are some problems in Computer Science for which there is no quick solution. That is to say that there is no clever formula for doing them - a computer has to use a brute force, "trial-and-error" type solution, the same as a human would. Examples of such problems are things like timetabling, the Eight Queens Problem and Sudoku. While the programs described above can be done using iterative or recursive methods, a recursive method called recursive backtracking is often then best solution for this type of problem.

In a nutshell the process is... try a value, if that works, try the next one, and so on. If a value doesn't work, then go back, change the previous one, and try again.

For example, with Sudoku (Python version), to solve a Sudoku puzzle:

1. place a number in the first empty space - use the rules (no duplicates in a row, column or 3x3 square) to make sure it's valid
2. repeat the process with the next empty space
3. if there are no valid numbers for that space, go back to the number and try a higher one

I also had a go at writing a program to create a Word Ladder. That's where you try to turn one word into another, one letter at a time, e.g. cat → cot → dot → dog. The process is very similar to Sudoku, but the method is a bit less precise as you can change any letter (and so my version might not always find the best solution):

1. swap a letter until we've made a valid word (by checking against a dictionary)
2. repeat the process with the next letter
3. if there are no valid words formed then go back and change the previous letter

This approach can be a bit more tricky to implement than a standard recursive function!