How to make the most of recursion in your code
For the most part, concepts in this article are discussed in the context of Python 3, but they are transferable to many other languages as well.
Well-known Google joke featuring recursion
Cracking the Coding Interview states that ?All recursive algorithms can [also] be implemented iteratively?? in its section on approaching technical interview problems using recursion.
Solving a Python problem iteratively might include using a for or while loop. These are some of the most common tools used for incremental problem solving in any coding language. Loops are great because, a lot of the time, their implementation is intuitive and straightforward.
However, there are times when iterative solutions can turn into barely readable nightmares.
Trying to write highly nested and complicated code on a whiteboard with an interviewer?s inquisitive gaze inspecting your work can be a surefire way to trip yourself up in a technical interview.
While switching from looping to recursion will not always make your code better, it is a great tool to have in your toolbox.
For a while, I was afraid of learning recursion. Upon learning that problems with a recursive solution inevitably have an iterative one as well, I was fixated on trying to solve every technical problem with loops.
However, as my technical interview skills grew, I encountered many LeetCode and HackerRank problems that cried out for recursion with their complexity. It was time to broaden the tools at my disposal.
What are Loops?
Diagram of a for loop and a while loop.
A loop is used to perform a repetitive block of code as many times as necessary for the program.
For loops, like the one in the example above, iterate over a sequence. We generally use for loops when we know how many times we need to execute a block of code. In the above example, we only need to do lines 2 and 3 for the number of names in name_list.
We might also need to loop for an undetermined number of times or until a certain condition is met. This might be a good time to use a while loop.
One way to return the length of a non-iterable Linked List might involve using a while loop to traverse all nodes like in the example above.
OK, so what is recursion?
Showing the base case and the recursive call in a recursive function on the factorial example. Image from https://www.slideshare.net/alhazmy13/data-structures-part5-recursion.
A recursive function like the one above consists of two parts: the recursive call and the base case.
The base case (or bases cases sometimes) is the condition that checks to see if we have gotten the information that we need out of our function. Every recursive function should have at least one base case, though there may be multiple.
In the factorial example above, we have reached the end of our necessary recursive calls when we get to the number 0.
The recursive call, as you may have suspected, is when the function calls itself, adding to the recursive call stack.
Stacks are LIFO (Last In First Out) objects, meaning that the last item that was added to the top of the stack is the first one to be removed from the stack later on.
Recursion works well for this type of structure because you can search multiple branching paths without having to include many different checks and conditions for every possibility.
For those of you who are familiar with data structures, you might notice that the image above of the file system looks a lot like a tree structure.
Trees and graphs are another time when recursion is the best and easiest way to do traversal.
Should I always use recursion?
Recursion seems really useful! Maybe I should use it all the time?
Well, like anything, recursion is best in doses. Recursion is a useful tool, but it can increase memory usage.
So let?s go back to the factorial call stack image from above. Every time we add a new call to the stack, we are increasing the amount of memory that we are using. If we are analyzing the algorithm using Big O notation, then we might note that this increases our space complexity.
There are times when we might want to pay this cost in order to get a short, useful algorithm, like when we are traversing a tree. But there are other times when there may be better, more efficient ways of solving this problem.
For many small projects, the call stack won?t hamper you program very much. However, once your program starts making many recursive calls, then you might want to consider the potential impact of your large call stack.
Photo by John-Mark Smith on Unsplash
Another thing to consider is that understanding and reading your code might sometimes be easier to do in an iterative solution.
Using recursion is great because it takes many of the incremental sub problems out of your hands.
But when you are try to fully understand the sub problems that you are solving and how they are being solved, it might be worth implementing an iterative solution. If this is not a feasible route, then, at the very least, diagram the recursive process undertaken by your code to deepen your knowledge.
What real life problems have you solved using recursion? Let me know in the responses below!
