Recursion it’s nothing else than the concept of a function that calls itself. This approach often leads to cleaner and shorter problem solutions, although it can be a little complex to wrap our heads around it at first.
Recursive functions need two things in order to work:
- A base case, or condition that is checked previous to execution (if this condition isn’t present the function call loop would run forever, but would lead to a call stack overflow error).
- A different input on each function call. This is what makes recursive functions make sense. If we always provided the same input to the function call, we wouldn’t obtain a different output.
Let see this through an common example. Let’s say we want to calculate the factorial of a given number.
The iterative approach could be the following:
The recursive approach could be the following:
As you see, recursion helps this function to be shorter and cleaner, but It could result cryptic as well if we don’t know what’s going on here, so let’s break it down.
First we check if the input number is one. As factorial of one is one, we return one if that condition is met.
The recursive magic is here, where we return the number, multiplied by the return value of the factorial function, with an input of the previous input number minus one. See that when we call the function again, we’re passing a different input.
If we called the factorial function with an input of three, the first recursive call we have an input of two, which will at the same time make another recursive call with an input of one. In that call, the ending condition (base case) will be met, so we won’t make another recursive call.
At that moment, each recursive call we make will return its return value to the “original” function, which itself will return 3*2*1, which is 6, which is the factorial of three. =)
A lot goes one behind the scenes of recursive function, but we don’t “see it”, which often makes them a nice and elegant option. Always remember you’ll need a base case and a different input on each call to make them work.