Intro to Recursion
Recursion can be a difficult concept to wrap your head around, but its definition is rather simple: recursion is when a function calls itself. Understanding what that means and using it in practice can be tricky, but there are a few key components to a recursive function and a fairly simple example problem that helps to make the concept a bit more digestible.
Key Components
There are two required components for any recursive function and one component that is often included.
- A Termination Condition
This is the component that is not always required in a recursive function. This is a piece of code that is put in place to protect against bad input. This condition will stop the function before running any recursion if the input given will cause an undesired result.
2. A Base Case
The base case is very similar to the termination condition because it also stops a recursive function. While the termination condition would be a fail-safe for bad input, the base case is the actual goal of the recursive function.
3. The Recursion
This is the component of the function that calls the function itself. When the function calls itself, the parameters of the new function call MUST be changed in some way. This ensures that the function will not get stuck in an infinite loop by calling itself with the same parameters again and again.
Example Function
One of the simplest problems to practice and understand recursive is a factorial function. You may remember from high school math that the factorial of a number is the number multiplied by “itself minus one” until you reach the number 1. For example:
4! (four factorial) = 4 * 3 * 2 * 1 = 24
This mathematical concept can be written as a function in JavaScript using recursion.
In this factorial example, if (n < 0) {return;} is the termination condition. It is impossible to factorial a negative number, so the recursive function should not even run if the input is negative. Next, if (n === 0) {return 1;} is the base case. Once the recursive function has run down to an n of 0, the recursion is done. We could change thee base case to if (n === 1) {return 1;} and receive the same result, however, this would not account for an input where n is equal to 0. Since 0! (zero factorial) is equal to 1, the way we have coded the base case in our example covers that edge case without impacting the result. Finally, return n * factorial(n - 1); is where the magic happens (the recursion). This is where we multiple the number n by whatever factorial(n - 1) equals. Below is a breakdown of the result:
Conclusion
Recursion is a pretty tricky concept to understand, especially if it is the first time you are seeing it. However, with a little practice, it will become easier to identify your base case and a pattern required to implement your recursive function. Recursion can be used to solve many real-world and interview-setting problems, so it is best to get comfortable with it!
