The Deceptive Simplicity of Recursion

When I started to learn about software engineering few things stumped me as much as recursion. I was able to grasp loops, data structures, and algorithms, but a succinct four line recursive function left my brain short circuiting.

Recursive functions are functions that call themselves, thereby repeating the logic they encapsulate until (hopefully) an end condition, or a base case is met. Since a recursive function calls itself and repeats its own logic, without a base case it would theoretically repeat forever, but in practice you’ll get a stack overflow when your function is called too many times.

The part that confused me the most about recursive functions was that I didn’t understand what a recursive function was doing when it called itself, it just seemed to call itself once, and suddenly problems that would normally need loops and iteration were solved with one line. Recursion was a cryptic puzzle to me, software engineers tend to call functions that use it “elegant” because of its simplicity, but that was lost on me. Compared to the intuitive explicit logic of a loop, all of the logic of the call stack that makes recursion work is implicit rather than stated in the function itself, so it just seemed like some weird magic happened behind the scenes to make my functions work.

When writing a recursive function, the code for the function to call itself is only written once, but it creates a chain of repeating function calls that depend on one of the calls eventually meeting the base case and returning so all previously called functions can return as well. Below is a simple recursive function that iterates through an array and prints the element at each index.

Iterating through arrays is not the best use case for recursion, but I’ve used it here for the sake of having a simple example. As you can see, the function recursive_print() is called within recursive_print() with slightly different parameters. When our function is called, it will print what ever is at array[i], which will always start at i=0. Our next call will do the same, except our parameters dictate that i be incremented by 1 with every new call of our function. This is where the iteration through our array will happen. As i is incremented with each call, the next element in the array will be printed. This will go on until our if statement at the top is true — our base case. Once our base case is met, our called functions will return one by one in order from the latest call all the way to the first.

Once I understood the fundamentals of how a function calls itself and creates a chain of events I was able to use recursive functions, but I still felt like I was missing a deep understanding of how everything happened under the hood. What was stopping my different functions from returning out of order, or returning at the same time? Why was it that my function calls waited for the base case to be met before returning? All of this became clear once I understood the call stack.

The call stack is indeed what it sounds like — a stack. A stack is a data structure that items can be placed (pushed) into and removed (popped) from. In order to reach the items underneath, items at the top must be popped, like getting a book from the middle of a stack.

When a function is called, be it recursive or not, memory is allocated for it to run in the stack. This chunk of memory is known as a stack frame. There can be several stack frames taking up space in memory, but only one of them will be active at a time. When a recursive function is called, each new call creates a new stack frame, and as the name implies, each new frame is “stacked” on top of the previous one. The frame at the very top of the stack is the active frame. Once our function calls reach the base case, the top active frame will return, and the underlying previous call will now be active, return, and this will repeat until our original call returns.

In the above animation you can see new calls to our function recursive_print() being added to the stack. each call increments i by 1, and calls recursive_print() adding another frame to the stack. Once our base case is fulfilled, that stack frame will return, and the following frame will return, and so on.

Once I understood the call stack I was able to appreciate why solutions that use recursion are considered elegant. They seem simple, but with one line of code you can set off an entire chain of events. In our example we used recursion to iterate through an array, but in practice recursion is best used in cases that loops can’t handle as elegantly, like traversing trees and graphs. Because a tree has repeating branches, the repetitive approach of recursion can be a powerful tool, but sometimes seeing an entire tree traversed in just a few lines of code still throws me for a loop.