Recursion: (In a Nutshell), (In A Nutshell), (In a Nutshell)
When it clicks, it clicks, it clicks, it clicks, it clicks….
Recursion can be a difficult topic for some early developers to pick-up on the fly. For me, that was definitely the case. It seems simple enough, but it takes most devs a couple of times learning the topic to have a strong grasp on it. Hopefully, this article can put recursion in the simplest of terms.
Recursion Defined
Recursion is a process (in our case a function) that calls on itself. Recursion functions continue to call on themselves over, and over, and over again until the conditional statement tells the original function to stop. Recursion must have the following two statements to be considered a recursive solution:
- Must call on the same function over and over; and
- Must have a stop point (a base case);
If either of the two statements above evaluate as false, it is not a recursive solution. Having a base case is probably the most important statement to have, or else your function will continue to run forever (known as a stack overflow, similar to an infinite loop).
Why Use and Understand Recursion?
Recursion is everywhere. It exists in a lot more places than I was originally aware of. Under the hood, JSON.parse() and JSON.stringify(),two functions used frequently to fetch data from a site’s backend, both use recursion. Recursion is also used frequently when traversing through nested DOM elements and traversing through objects. Finally, when using complex data structures (trees, graphs, heaps, etc.), recursion is almost always need to solve the problem at hand. In most cases, the problem could be potentially solved without recursion, however, recursion could be a required tool to have to have a cleaner, easier-to-read solution. Any developer would agree writing a recursive solution would be cleaner when compared to a for loop with 5+ if/else statements.
Factorial Example
Let’s look at an example of recursion in action with a factorial (e.g. 4! === 4 x 3 x 2 x 1, or, n times each number less than it down to 1).
Like we said above, we don’t always have to use recursion to solve a problem. The above, can take in any number, and multiply it by every number below that number down to run. This determines a factorial iteratively.
Now, the same solution with recursion:
With the above code block, we’re calling on the same function (in this case factorialRecusive) continuously until we reach 1. Our end-point, the base-case, is on line 2. Without that statement on line 2, line 3 would continue to run to -Infinity. This is a simple example of recursion: both of our statements from our recursion definition have been satisfied:
- We are calling on the same function (factorialRecusive) over and over on Line 3;
- We have a stop point (a base case) on Line 2.
Fibonacci Sequence
The above demonstrates solutions to determine the fibonacci sequence, a famous arithmetic where every number is the sum of the proceeding two (e.g., the start of the Fibonacci sequence is: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]. The sequence continues on to infinity, and both the above code blocks calculate the sequence to what ever number n equates to. With the iterative solution, we know the sequence will always start at [0,1], so we set that as a result variable. We then are looping through all numbers through n, and pushing them into the results array based on the proceeding values. I think we could agree the recursive solution is MUCH cleaner. That being said, it is MUCH slower. It creates a tree, and if n were to be 100, the tree is massive. You can use memoization to reduce the runtime, by implementing a cache.
Helper Methods with Recursion
Helper methods are common to use with recursion. When you need to set an empty results array, a common bug would be returning that empty array over and over again recursively. Lets see one in action, collecting odd values from an array:
The helper function is the pure recursion function. We continue to run it, pushing the odd numbers in the results array. If the result declaration was made inside of our helper function (the recursive function), the result array would continue to be reset as an empty array every time the function was called. This wouldn’t return our desired result. We could set the result array as a global variable, but those should be avoided at all costs, so we define it within the scope of another function. This is a common approach with recursion, and helper functions are needed frequently to tackle solutions.
Conclusion
Hopefully you were able to tackle recursion with the above examples on your first attempt. If not, keep reading and practicing recursion problems. When recursion clicks, it clicks, and clicks, and clicks, and clicks, and clicks…(oops, we have no base-case conditional, we’ll now be clicking to INFINITY!!!)…Happy coding.
