Recursion Explained in simple terms

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.

Factorial Example

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;

something * something_else * a_smaller_something * etc

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.

  def factorial number
    return 1 if number == 1
    number * factorial(number - 1)
  end

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 number is 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)

  factorial 5
  #=> 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.