Recursion, Recursion, Recursion featuring Fibonacci
Recursion is arguably one of the most confusing concepts in the world of programming. We see it come up in interviews, algorithm challenges, and sometimes in the real world code, but what is this elusive concept, and why the heck do we need to know it?
In computer science, recursion is a programming technique using function or algorithm that calls itself one or more times until a specified condition is met at which time the rest of each repetition is processed from the last one called to the first.
- CS240 — Lecture Notes: Recursion
So really, all recursion is, is a function calling itself. Simple right? Right, it is simple and can make for some very elegant solutions to problems that involve multiple passes to complete, like some cases where we would normally use a loop. Some very popular interview questions could be solved with recursion that you can check out in this great post “10 Popular Coding Interview Questions on Recursion”. It is important to note that recursion is ONE method to solve a problem, not the only method, and in some cases, a loop may be a better choice. So let's look at a common Fibonacci sequence problem that could use recursion, and compare that to its solution using a loop to see what the heck all the fuss is about. I will start with the looping solution.
Quick side note here on what the Fibonacci sequence is. The sequence starts with 0, but begins working at 1, and will increment based on its previous value. So 0 + 1 = 1, 1 will become our “result”, and the larger value in our expression will be assigned to “previous”, and we will continue. 1 + 1 = 2, now “result” = 2 and “previous” = 1. Here is one more to make sure it's clear what's happening. We plug our values into “previous” + “result”, and since “result” = 2 and “previous” = 1, or expression is 1 + 2 = 3. This will continue for as many cycles as we indicate with the argument “n” in the following functions.
NOTE: lines prepended with “//” are comments to help guide understanding, not actually part of the code
function fibonacci(n) {
//check if the base case condition is met
if(n < 2) return n//set our intial values for previous and result
let previous = 0 let result = 1//start our loop with i starting at 1, since we have done our first //sequence manually by setting previous and result above
for(let i=1; i<n; i++){ //set a varible for the new value we get from our sequence
let newValue = result + previous //update the values of previous and result
previous = result result = newValue//check if we have done enough sequences to equal n -1, we //subtract 1 since we manually did our first sequence by setting //the previous and result variables above
if(i === n - 1) return result }}fibonacci(10) //Output: 55
This first solution makes sense to me. We first take care of the base cases, set our starting numbers, and move through adding them to the previous number as many times as directed by the argument “n”. To me this function looks like the process we would use to do the Fibonacci sequence with paper and pen, and therefore can be understood; this next function, on the other hand, boggled my brain. This is our recursive solution to the Fibonacci sequence.
function fibonacci(n) { //check if the base case condition is met
if(n<2) return n//return this same function added to itself, with the arguments //being 1 and 2 less than our starting value
return fibonacci(n-1) + fibonacci(n-2)}fibonacci(10) //Output: 55
Ok, this may just be me, but I’m wondering what the heck happened here? We just talked about how the sequence was taking the previous value and adding it to our current value, where is this even happening?! AND what are we returning, there is no variable to save the current and previous values in, and the only condition we have to meet is if “n” is less than 2, but then we would just return “n” which if it meets that condition could only ever be a 1 or a 0.
Yeah me too people, it’s confusing, but look at how clean and simple the code is. In just a few lines we were able to get the same results as the longer looping solution. So what is happening here to give us the same answer?
Well, we need to understand how a recursive function resolves its returned values. Since we are returning a function, we will return the return value that results from that given function; returning the return of the returned functions… welcome to recursion folks, things will recur.
We know that the only condition that we have will return a single value is if the argument “n” is less than 2. Let's walk through the steps to see when this condition is met. We will use 6 for the value of our argument “n”, and the result of doing 6 Fibonacci sequences will be 8, just trust me on that and we will see each step below.
This is tree represents each step in our recursive function. Can you see how we return 8 from this function? Yeah, me either.
In this tree, we can see thirteen different function calls, represented by the red and dark green cards, as well as the four blue functions with nothing below them, that would fulfill our one condition to return a value; is “n” less than 2? But how in the world does that end up equaling 8? Let’s take a look at how this tree would resolve the returned values.
If the value is less than two, then return that value. So each of these functions would return “n”, either a 1 or a 0. Ok so we have talked about the return value if our condition is met, but what about when we return the two Fibonacci functions added together?
Spoiler, these functions being added together is where we will actually get our answer from. For each of these functions that have returned values, we have to add them (as our function stated, return Fibonacci(n-1)+fibonacci(n-2)) and THAT value is what will be returned in the functions that did not meet our condition of “n” being less than 2.
The numbers in green are the sum of the returned values from the functions below that function. As you can see, most of them evaluated to 1, because we have a 0 as the other added value, but the function furthest to the left evaluated to 2! Now we are getting somewhere! This process will continue until we reach the top function where we will have our answer.
Woah, so that little bit of code in our recursive function did all of this! I hope that having the steps drawn out helps you to see that our recursive function IS doing the same thing as our more declarative looping function.
So when do we use a recursive function? Well, all the time right? It’s much shorter to write and makes me feel smarter than that lopping function where I told you exactly what was going on…
And here lies the problem with recursion. You’re right, it is as elegant as a black-tie affair, as streamlined as a fighter jet, and as easy to write as your own full name, but when someone else sees it the first thing they will think is “What the heck does this function do?”.
There is a programming adage that says
There are only two hard things in Computer Science: cache invalidation and naming things.
— Phil Karlton
Naming things is difficult, not because it's hard to think of something to call it, but it’s hard to think of the RIGHT thing to call it. What can we call this thing that lets other people looking at my code know what it is, what it does, and maybe why it is here. Take our Fibonacci function, for example, we know it has something to do with Fibonacci obviously, but what is “n”, and what is the function actually doing? Does the function start the Fibonacci sequence on the number “n” or is something different happening? This can be figured out by really looking at the function and working through it, but we as programmers should not leave future programmers in the dark about what we are doing. Having to take 10 minutes to understand what a function that is only 3 lines long is tedious and ultimately avoidable. The first example using a loop could have more explicit names, but as it is it is still much more verbose than the recursive option.
In conclusion, recursion is an interesting beast and worth knowing for technical interviews and as a solution to repetitive coding problems, but is it the best? Most of the time no. We want our code to be clean and understandable. We want our variables and functions to be declarative, they need to tell us what they are for right there and then, not after we take them out to dinner and a movie and really get to know them. Don’t get me wrong recursion can be a great solution to many coding problems, but if we choose the recursive solution we NEED to give three times more attention to how we are naming things and maybe throw in a comment or two to help others understand whats going on quickly and concisely. So go forth fellow coders, into the infinite mirror of recursion and find the secrets nested deep within.
And if you forget to add a condition to meet for the recursion to end you will be lost forever in an infinite loop, so good luck!
Happy Coding!
