Recursion!
What is it?
Recursion in its simplest definition is calling a method or function inside of itself. In other words, within a function definition, there is a function call to itself! It’s basically inception….
Conceptually, we can think of recursion like the opening of Russian dolls. Inside each of the dolls we open, there’s a tiny piece of paper with a number, perhaps we’re adding something or subtracting something. We know we have to open each of the dolls, but we don’t know how many, and only at the end, can we know what the result is.
Let’s not give recursion too much credit though or else we become too afraid to use it.
There are three concepts that you should immediately think about when considering a recursive approach to a problem.
- Base Case
- Recursive Case
- The idea that you’re breaking down a problem into it’s simplest step and doing that step over and over again until you’ve reached your Base Case or “The End of the Line”
The Base Case is a condition that must be met in order to stop the recursive call in your function. Otherwise you will infinite recurse into stack overflow. Think of this as the condition you set in a while loop, that allows the while loop to cease executing.
The Recursive Case is the condition that calls the function within itself. This allows the function to progress to the base case.
Back to our Russian doll analogy. We open the doll, find the number and keep it in the order you opened them, then open the next doll(Recursive Case). After all of the dolls are open(Base Case), we can start adding the last number to the second to last number, then that number the next two and so on until you arrive at the sum.
Recursion goes a lot more in depth when you bring `tail recursion` into the mix. That is passing an accumulator in as an argument to your recursive call so that we don’t need to follow the call stack in order to return the sum.
In the Russian doll example, you would just total everything up as you go, and at the end you would return that as the sum.
Recursion is super powerful, and is easy when you keep the 3 main points in mind, don’t be afraid to give it a try and reach out if you’re struggling with it conceptually.
Leave a Reply