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