Recursion is a type of problem-solving used in computer science. It sounds a little abstract at first, but stick with us and we’ll explain. It’s actually simpler than it sounds!
Recursion is when the solution to a problem uses smaller instances of the problem itself. In programming terms, recursion is when a function calls itself.
Example of Recursion
It’s easier to explain recursion with a concrete example. Consider the factorial function. In math, a factorial is written using an exclamation point, like this:
8!
A factorial is calculated by multiplying the number by the previous number and the number before that and the number before that, all the way down to 1. So, the solution to 8! Is:
1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 = 8!
So, how might we use recursion to solve a factorial problem with coding? The factorial of any number, n, is a composite of the factorials of all the numbers before it. That is, the factorial of 8 is the same as 8 times the factorial of 7. That is:
8! = 8 x 7
It is also the same as 8 times 7 times the factorial of 6, or:
8! = 8 x 7 x 6!
In order to solve the factorial, you must first solve many smaller factorials. That’s what makes this an example of recursion.
Example of Recursion in Java
Now let’s see what this looks like in coding. First we’ll create a function called factorial, which takes an integer n as an input and returns the factorial of that number. The function factorial will call itself, which makes it a recursive function.
The important thing to consider when writing a recursive function is that you must provide a base case that does not call the function. When the base case is reached the function will return the output. Without a base case, your recursive function will continue to call itself forever!
Our base case for the factorial function is when n=1 or n=0. In both cases the factorial is 1. We set the output for the base case to 1.
What is the Base Case?
We touched on this briefly above but, to recap, a base case is the only part of a recursive function that does not call itself. It is important to include a base case in a recursive function because, without it, a function will continue to call itself without reaching a stopping point.
A base case does not need to call the function again because the output is written into the code. For a factorial function, the base case is when n equals 0 or 1. 0! and 1! both equal 1. To create a base case we say that when n=0 or n=1, the solution is 1.
That wasn’t so complex was it? If you’re ready to learn more about the principles of problem solving in Java, browse our Top Java Tutorials or test your knowledge using these Java Practice Problems.
