Recursion

What is recursion?

To start a recursion is looking to solve a problem, by breaking it down into smaller chunks, which contribute to the final answer.

If it is calling itself, then it is commonly known as a recursive function.

By breaking down the problem at hand, it can then lead to a quicker understanding and solution to the problem.

A simple example might help here, explaining through factorial:

4! = 4*3*2*1 = 24
simple factorial example

From studying maths at school, the simple example above breaks down as:

  • The result 24 is a product of all the values from 4 down to one.
  • As each value that makes it up is known, it then can be seen how the result is made up.
  • The above can be viewed as a recursive function as it keeps repeating on itself until it reaches one, the base.
  • The recursion knows there are three steps before it reaches one; this is where the breakdown into smaller chunks comes in.

So it could be broken down as follows:

Step 1
4*3 ---> Not reached one, try again from the start.
Step 2
4*3*2 ---> Not reached one, try again from the start.
Step 3
4*3*2*1 ---> Reached one, so the recursion stops and the result is outputted.

Steps 1 to 3 are the steps within the function it takes until it reaches the base value, where the function stops and outputs the final value calculated.

Attributes of a recursion

  • A function which calls on itself, this is the repeated steps above until it reaches the base of 1, meaningĀ it doesn’t loop infinitely.
  • Must be possible to break the problem down into smaller parts.
  • As the problem gets broken down, it must become easier to solve without further calculations.
  • Once a smaller part has calculated, this just becomes part of the answer to the overall problem.

Things to watch out for when using recursion

  • Ensure you always have a base value; without it, you could encounter an infinite loop.
  • Not having the ability to break up the problem into smaller steps won’t allow the calculation of the final answer.

Why use recursion?

  • It helps to break up a complicated task into smaller bits.
  • Assists a programmer to see what steps have already coded for so can be solved with other functions already written.
  • Where there are multiple recursive functions, allows to see if similarities in steps, hence only need to programme once for them.

A good source to provide further knowledge can be found hereĀ Wikipedia – Recursion

Data analytics Ireland

Leave a Reply

Your email address will not be published. Required fields are marked *