Someone once said, in order to understand recursion, one must first have to understand recursion.
Did you get it?
There are many many seemingly complex problems can be implemented quite elegantly using recursion. However, most of the time they require a good understanding of how recursive calls work before the solution can be implemented.
When I first started, I found the concept of recursion really hard to wrap my head around, but the truth is, it’s sort of like a roller coaster ride. It seems scary as you stand on the ground looking up, you finally give yourself enough prep talk and go for the first time, it’s full of unexpected variables that first time you play. But not so much the second time, “meh” on the third time … the difficulty quickly decreases as frequency input increases. Sort of like a logarithmic time complexity, but that’s for another post.
A popular questions I have seen is, “so how do I know when should I use recursion?”.
Generally, a problem is recursive when it can be built off of same subproblems, over and over again. When you hear a problem that sounds something like “design an algorithm to compute the nth x …” or “write code to list the first n of y …” or “implement a method to compute all of z …” , you can start thinking about recursion.
Alright, so now that you have a better sense of when to use recursion, the next question is, how to get better at it, what routes do you take to approach the solution? Besides putting in more time to research and practice more about the concept, what else could you do? Let’s spend some time thinking about the problem and ask your self these questions:
- What is the smallest, non recursive aspect of your function that it needs to perform? For example, if you need to traverse through a tree-like data structure, and recursively map every nodes and their children to form a new tree, the smallest piece would be just to map the value on just one node. Write a function to handle that case and only that case.
- Cool, so now let’s identify what will make the function need to continue, and what will make it stop. Which will make up the recursive part and a base case for your function, respectively. LPT: if you get a “Maximum Call Stack Exceeded” error message when you function is invoked, chances are you have a bug in the base case, otherwise if the function doesn’t run at all or stop mid way through, double check your condition.
- Once you get your base case and null case handled, write the recursive call. You will need to determine before hand if you need to accumulate any results, or if you need to return anything. Then start writing your recursive calls.
If you just start out, I suggest you to follow the bottom up approach, which is to knowing how to solve the problem for one element, them figure out how to solve the same problem for two elements, and then three, so on and so forth. It’s a very intuitive approach, the key is the get you to think about how you can build the solution for one case off of the previous case.
The goal when you first start out should not be how clean & concise your code is, but instead how easy could you reason your code to a third person (sort of like the rubber duck method).
Now that you’ve gotten a better understanding of recursion, let’s start with some factorial or palindrome permutation type of problems, and in no time the roller coaster will gets much, much less scary.