Hey everyone, today we’ll be looking at recursion and some of its characteristics along with an example. First off, I’ll talk about what it is, why it can be an important tool in your tool belt.
So what is a recursion?
Well according to the wikipedia page on recursion, it is “a method of solving a problem where the solution depends on the solution to smaller instances of the same problem. To put it simply, you can call on the defined function within the logic block of that same function. This is different from creating a function that is iterative. Iteration is where a function repeats a series of steps until some condition stops it.
Should I use recursive or iterative functions?
This honestly depends on each use case and what data structure is being used. For example, a binary tree is a great chance to implement recursion because it’s a data structure that can have many smaller trees as you traverse from node to node. It would make sense to use recursion here for simplicity compared to an iterative method. Iteration is great for “simple” data structures such as an array! It can even be argued that iteration is easier to read and that recursion is “syntactic sugar”. Though the answer of when to use recursion or iteration can be vague and ambiguous, there’s really no hard rules. Asides from some cases where it is impossibly hard not to use recursion, it boils down to what makes sense in whichever specific problem that you’re currently trying to solve. Though there can be a vast difference in terms of time/space complexities between the two due to the nature of each method. More on that in the next blog.
An example for a problem on LeetCode
A problem I recently completed is what prompted me to write this blog today. On LeetCode, the problem “add digits” is listed below.
Just to challenge myself, I tackled the problem by implementing a recursive solution, just to see if I can flex my brain a bit harder.
A trick I first realized with this problem, is that the output will always be a single digit. You can’t add one value to another value when you don’t have the second one. Secondly, I thought of a recursive approach because of the explanation given. You’ll be reducing the number until it falls within the single digit range. So off I went and did just that! Here are the general steps to do so.
- to avoid an infinite loop, you’ll have to declare some logic to break out of the recursion every time it is called. Example Lines 2 and 3 within the if statement does this.
- The next block of code is the logical step portion. In this case, line 5 will essentially turn the multi-digit number into an array of individual numbers.
- Line 6 will then call upon the addDigits function with the sum of the object in line 5.
- It will then recursively run through the addDigits function from the top again, checking the num that was previously passed, then do a bit of number crunching until it reaches a valid output and is returned from line 3.
Hey the runtime is pretty good! Though my memory distribution is pretty bad. I could always try to refactor and make both the runtime and memory distribution to be as efficient as possible, but the point I was leading up to is that there are tradeoffs to everything you do. This goes back to the idea that every situation needs context which will dictate the use cases. If “speed” or absolute best time complexity is your goal, then you can make decisions to work towards that. If saving space and reducing space complexities is your goal, then the same idea applies. Though I believe it’s best to avoid extremes and keep things balanced.
