Recursion when used in a programming or computer science context simply means when a part of your program calls itself.
This sounds complicated, and trust me the first time you try and get your head around this it can be tough, but lets work through an example.
This example will be in Ruby, don’t worry if you don’t know Ruby, I will be explaining it line by line.
Say we need to write a program that lets us work out the factorial of a number. The factorial of a number is just the number multiplied by a progressively smaller figure until we get to 1.
The factorial of 5 is 120 because
5 * 4 * 3 * 2 * 1 = 120.
Our code for our program would be really big if for each number we wanted to get the factorial of we wrote out;
Instead we can try and break down what a factorial does and write code to follow these rules.
We know three things.
- It starts with a number that we want to know
- It keeps on multiplying by smaller and smaller numbers
- It stops when it gets to one
We also know that from looking at our
5 * 4 * 3 * 2 * 1 = 120 example that if we knew the factorial of 4 (
4 * 3 * 2 * 1 = 24) we could just write
5 * 24 = 120. In other words, a factorial is just our main number multiplied by the factorial of the next number down from it.
Lets write this in code.
On the first line we have created what is known as a Method. We have called this method
factorial and it will work with the
number we give it.
When it gets a
number the first thing it does is look to see if the
1, if it is 1 then we just return 1 since the factorial of 1 is 1. That is line number two.
On line number three we take that number and multiply it by the factorial of the number one less than it. So if my number is 5 it would be multiplying 5 by the factorial of 4.
In Ruby we can then test it by asking for the factorial of 5 (which we know is 120)
How do we know this is Recursion?
We know that the method we have made is recursive (and therefore an example of recursion) because in our method was called
factorial and in it we call a method called
factorial. The method has called itself.