Demystifying Recursion
After completing my first linked-list someone somewhat condescendingly told me I really should have built it recursively, as if completing a linked-list wasn’t something to be proud of on its own. This marks both the first time I had heard of recursion and the beginning of my intimidation of it. By the time I built out a merge sort I was using recursion, but certainly not understanding it. I believe someone told me “you just have to believe that it will work.”
I created some visual models to help me understand what was going on, but until I knew more about the stack and how programs are run under the hood that I really grasped what was going on with recursion.
Shall we take a peek under the hood?
The Stack:
One of the most approachable explanations of the stack I’ve encountered comes from The Rust Programming Language book.
Both the stack and the heap are parts of memory that is available to your code to use at runtime, but they are structured in different ways. The stack stores values in the order it gets them and removes the values in the opposite order. This is referred to as last in, first out. Think of a stack of plates: when you add more plates, you put them on top of the pile, and when you need a plate, you take one off the top. Adding or removing plates from the middle or bottom wouldn’t work as well! Adding data is called pushing onto the stack, and removing data is called popping off the stack.
The stack is fast because of the way it accesses the data: it never has to search for a place to put new data or a place to get data from because that place is always the top. Another property that makes the stack fast is that all data on the stack must take up a known, fixed size.
Methods, Frames, and the Stack:
In a Ruby program, when a method gets called a frame goes onto the stack (push). This frame is essentially an instance of the method, holding local variables, arguments that have been passed into the method, which instance it belongs to, where to return to once it is complete, and a pointer to the method itself. Once the entire method is done the frame gets pulled off the stack (pop).
For the sake a simplifying things, I’m going to include the code for each method and pointers to where we are in the method to help us all keep track of what is going on. Remember though, the frame has a pointer to the method not the method itself.
If I were to add a second method that gets called by the first, it might look something like this:
Here grade_assignment gets called and its frame pushed onto the stack, within this method total_score is called and its frame gets pushed onto the stack as well, while grade_assignment pauses and waits. Once total_score is done its frame pops off the stack and we return to grade_assignments which has been waiting for us. It finishes and then its frame gets popped off the stack as well.
In the most basic way, a frame go onto the stack when the method is running and because we often build methods which call to other methods the pile can get rather high and cause some interesting behaviors.
Recursion
According to Oxford Dictionary:
recursion: (noun) The repeated application of a recursive procedure or definition.
Gee thanks, so helpful. But, if we look at it’s root we get this:
recur: (verb) Occur again periodically or repeatedly.
So, a recursive method is one that recurs, and specifically recurs by calling itself until some condition is met.
Let’s put this together with the stack to see what it looks like.
Looping Recursion
I think the easiest type of recursion is where a method does its thing and as the last part of its commands calls back to itself again.
Imagine you are in a classroom with a bunch of kids sitting in a circle waiting to start the day. Each child is going to say good morning to the child sitting next to them. Once a student no longer has a neighbor that has not been greeted the cycle stops.
Looping Recursion and the Stack
Let’s turn our attention to what that looks like on the stack. It gets a bit more complicated looking:
Here we call the initial say_good_morning, which calls itself again and again and again until the return statement is triggered. Each time say_good_morning gets called from within say_good_moring the current say_good_morning’s frame needs to wait around until the say_good_morning it called is off the stack in order to hit its own end line and pop off the stack as well.
Vortex Recursion
This is how I think of it, since you keep dipping down into new paths. There is probably a more technical term but this one makes sense to me. This gets a bit more complicated, so stay with me:
Imagine a scenario where students are lining up for school pictures, in height order tallest to shortest. Each student already happens to know one student taller than they are and one student shorter than they are.
In this method, we start with the first kid, any kid. If there is someone taller than they are, this student waits and the taller student steps up, then we repeat the process. If there is someone taller, that student steps up until there is no one who knows someone taller. This taller student gets in line and then their shorter checks to see if anyone is taller than they are. If so, we go back to looking for taller people, if not this student gets in line and we then check for their shorter student. We keep going with checking for taller students first, the student getting in line themselves, and then checking for shorter students.
Vortex Recursion and the Stack
Let’s try this with 3 students.
We started with the first student, then went to the their taller student. From here, even though we can see from the diagram that taller has no more connection, the program is going to check each of those, start to run the method, trigger the return and pop the frame off the stack. Notice how in this style of recursion the stack is going up and and down and up and down instead of the straight up and straight down of our looping example.
Let’s check the shorter student now.
From the shorter student, we check if there are any taller students, which there aren’t, shorter gets in line and then we check if there are any shorter students, which there aren’t any. Finally shorter’s frame pops off the stack, we return to the initial student who has been waiting, they pop off the stack and everyone is in line.
While this was a total of 20 steps just to get these three students in line, computers are super duper fast so as a user we can’t even tell.
I encourage you to think through how this series of method calls would be impacted if we add two more students to the combination.
Summary
Wow, that was a lot to think through. Let’s review the essentials of what’s happening when run a recursive method.
- The current method’s frame gets pushed onto the stack.
- When it calls back to itself, making the same functionality recur, another version of the method’s frame gets put on the stack.
- A frame can only come off the stack when ‘end’ has been hit and there is nothing else to run.
At it’s heart, recursion is when a method calls itself to run again with new data passed into it. A method that recurs.
