Life Without Recursion

Introduction

Recursion is a very common subject covered throughout computer science education. Recursive solutions provide interesting approaches to complex problems. They can be fairly intuitive and allow for more interesting ways of structuring iteration. Splitting one large problem into a multiple smaller problems while still maintaining a degree of control over the flow of the iteration is what makes recursion so useful. 

Recursion can be useful for complex data structures, like trees

Even though recursion opens the doors to more involved processes, it comes with several downsides that I believe often get swept under the rug. Recursion may be convenient in many cases such as the first implementation of an algorithm. However, high quality programs and final builds should consider the drawbacks that recursive functions come with.

Debugging

Recursive functions are often more of a hassle to debug compared to iterative approaches. Constantly stepping in and out of function calls when debugging can become tiresome quickly and lead to less productive debugging sessions. Splitting each iteration into an entirely separate function call can make it easy to lose track of the context as local variables are either no longer in scope or replaced from a new function call. 

This can become an issue when trying to reason through the problem as the state of the solution is split across several stack frames. With iterative approaches, the entire state of the iteration can often be stored in a couple variables which makes understanding the current state of the solution more feasible. This can also reduce maintainability as obscuring the state with function calls can make the problem less approachable than if the whole state was front and center in a loop.

Performance

Calling functions recursively incurs some noticeable overhead in regard to copying data. Temporal locality also suffers as copies of data are being modified, rather than just an individual variable. In order to reduce function parameters and get back some locality, programmers may bundle data in awkward ways that force indirection and additional overhead. Some languages have systems to allow for better recursive functions in the form of local functions, for example. 

Recursive memory footprints are often larger than iterative ones

Function calls also make optimization much harder from both the compiler’s standpoint and the programmer’s. It can be difficult to see into a function call and assess what variable can be compacted, or what calculations can be sped up with SIMD, for instance. Recursion can also lead to one function being split into several functions. This can lead to the code to a solution becoming more spread out and disjointed, which may prevent the programmer from seeing patterns that may arise from doing things iteratively.  

Alternatives

There are plenty of strawman examples of where recursion is terrible like finding a fibonacci number. A more serious example I recently encountered was traversing a red-black tree. I used my own stack data structure instead of the call stack to mimic the benefits of recursion. I did this by using an array of the same size of the max depth of the tree, and a variable to store what depth the process was in the stack. By keeping everything in one function call, no compromises needed to be made when considering what data to include in the recursive function as all the local variables were in scope.

I have also made an iterative version of merge sort, which is almost always presented in a recursive manner. The iterative version of merge sort is slightly more complicated and requires some addition analysis such as the expected depth of the sort. In this instance the conversion was a bit involved, but that is expected when trying to convert a function to a high quality state.

Iterating over the depth of the sort mimics recursion

Conclusion

Recursion can be somewhat convenient when solving a problem, but in the long run it serves to be a rather subpar solution. It reduces maintainability by becoming harder to debug and reason about. It also hinders performance by reducing locality and adding unnecessary overhead. Almost any recursive solution to a problem can be made into an iterative one, so try and see what recursive solutions you’ve written that can be transformed into an iterative one.