# When to loop? When to recurse?

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 name in name_list: # we go over every name in the list
name = name.title() # we change every name
counter += 1 # each time, we add 1 more to the counter
``````
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.
``````def length(self):
"""Return the length of this linked list by traversing its nodes."""
node_count = 0 # initial count is zero

# Loop through all nodes
while current is not None:
current = current.next
# add one to the counter each time
node_count += 1
# return the total length
return node_count
``````
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.

## Okay, so what is Recursion?

Image from https://medium.com/@williambdale/recursion-the-pros-and-cons-76d32d75973a

A big difference between recursion and iteration is the way that they end. While a loop executes the block of code, checking each time to see if it is at the end of the sequence, there is no such sequential end for recursive code.

Like the horrifying Winnie the Pooh comic above, a recursive function could go on forever without a condition to put it out of its misery.

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.

## When Should I Use Recursion?

Recursion is made for solving problems that can be broken down into smaller, repetitive problems. It is especially good for working on things that have many possible branches, and are too complex for an iterative approach.

One good example of this would be searching through a file system. When you start at the root folder, and then you could search through all the files and folders within that one. After that you would enter each folder and search through each folder inside of that.

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 your 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.

Stack of Books. 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.