Recursion in the simplest terms
Any time the subject is brought up my brain would immediately start to melt. It didn’t help that almost every instructor goes on about how difficult it is for newbies to grasp. All I knew about recursion was that I needed to call the function within itself and then my brain would stop working.
While talking about the base cases and recursive cases one tutoring session my instructor at Operation Spark, Ryan McFarland, said something that really made it ‘click’ for me. He said, “the base case is the conditional we want to meet/where we want to end and the recursive case is ONE thing we can keep repeating to reach the end/make the base case true.” I’m still no expert but after that I was able to work through problems without Google and hopefully you will be able to as well.
Let’s start from the beginning. What is recursion? Recursion is just a function that calls itself. Sounds simple enough, yeah? Try not to overthink it. To build a recursive function we want to start with building a plain function structure like below. Here I have named the function ‘recursion’.
A good recursive practice problem is using recursion to ‘loop’ an array and return the sum of all the numbers. First I am going to refresh you on how we do this with a simple for-loop. This exercise can be found on multiple sites, I am working from David Tang’s ‘Learning Recursion in Javascript Part 2’. To loop and return the sum of an array is fairly simple, I’m sure you’ve seen it before.
When looping we are able to assign each value in the array to i then easily add each value to the sum variable that was originally set at 0.
Back to recursion. Two things that will never change about recursive functions, they will always have a base case and a recursive case. (sometimes more than one but just one in this example). The base case is a condition we want to meet or where we want to end/stop recursing. We are adding the sum of digits so we know our base case will return a number and since we are adding digits in the entire array, the condition we want to meet is an empty array (because we have recurse through it).
The next and final step is to make a recursive case. This is the part of the code where the function finally calls itself. When thinking about the recursive case, you should consider ONE step you can repeat to get to the base case.
To imitate looping an array, in the recursive step we will return the first digit in the array; array[0]+ recursion call with slice method. We use the addition operator because the elements in the array are numbers.
Something I didn’t understand when first learning is that the recursive case is literally the function call and ONE step that will keep happening because the function will keep calling itself until the base case is TRUE. The recursive case is read right to left. First javascript will slice off the first digit in the array with array.slice(1) and add it to the call stack and keep doing that until we reach the end of the array.
A call stack is like filling a Pringles can with data chips. We are slicing the first number-chip off, putting the chip in the empty can, slicing the second-number chip and putting it on top of the first chip, and so on until we reach the end of the array. Once we reach the end of the array, we will start to take the chips out of the can one by one, starting at the top (no choice with a Pringles can!). As we take them out we will add them up. This is what a call stack would look like courtesy of David Tang’s ‘Learning Recursion in Javascript Part 2’.
Read more in-depth info on call stacks here:
Conclusion
Recursive functions can return any data type. If we want to return an array, our recursive call would need for us to concat the values since adding them like the sum function would not work on array. Similarly, if we were working with an object, we would use bracket notation; multiplying numbers, we would use the * symbol and so on.
The main thing someone should get from this article is before beginning to solve they should consider what type of data they want to return (number, array, obj). Recursion is a function that takes a base case that we want to meet (always an if statement). The recursive step is calling the function inside itself and one thing we can repeatedly “do to” one piece of the data until we reach the base case. Hope this helps!