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