Iteration and recursion are key Computer Science techniques used in creating
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.
If you want
visual analogies of recursion, I'm compiling some examples here.
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
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:
var loop, answer;
answer = 1;
answer = answer * loop;
dim loop, answer
answer = 1
for loop = 1 to n
answer = answer * loop
factorial = 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:
if (n == 0)
return n * factorial(n - 1);
if n = 0 then
factorial = 1
factorial = 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!
You can also see Python versions of the
recursive versions on my
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
Python code for this method in Repl.it.
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
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
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).
an implementation of this method in Python on
my Repl.it page.
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.