My first big a-ha moment! (Or, if I can learn recursion, you can too.)
The path of learning how to program is long and often difficult, but it is full of these wonderful a-ha moments. It is these highs that can often power programmers through the lows of uncovering the solution to the problem at hand.
After I completed Dev Bootcamp’s program, I became a mentor and tried to help others understand this concept of highs and lows, and how not to be discouraged. During my time as a mentor I was often asked similar questions by different students. One of those questions was ‘can you help me understand recursion?’
I remember the day we were introduced to this concept. I sat in confusion. It’s a tricky thing for the mind to grasp, initially. Story after story and code example after code example just stirred the confusion, it did nothing to help clarify recursion for me. Until one simple function with two simple console.logs gave me my first big a-ha moment!
But first, what is recursion? Well, if you turn to google, it might not be super helpful. Programmers sure do love to make jokes.
In short, recursion is when a function will call itself with a modified variable, sometimes repeatedly, until finding the answer. (Or not finding the answer.)
When I was learning the concept, I was given a story about a king who ordered a countryman to find the heaviest stone in the land, so the countryman employs a village of people to weigh two stones then move the heavier one up the chain of persons weighing stones. The story made sense regarding how to divide work, but not how the manipulated data moves up the stack. So, I like to think of it differently…
The Great Cake Recipe
Imagine you are trying to remember your great grandmother’s cake recipe. You remember some of the ingredients, but not all and not the exact measurements.
You call your mother. She has more information than you, but can’t remember all the specifics, so she puts you on hold, and calls your aunt.
Your aunt remembers more than the two of you combined but, again, not all the specifics. She puts your mom on hold and calls your grandmother.
Your grandmother has more ingredients and measurements, but needs one more detail, so she puts your aunt on hold and calls her sister, your great-aunt. Now you, your mom, and your aunt are on still hold.
Your grandmother gets the last of the recipe details, hangs up with your great-aunt and connects back to your aunt, fills in her missing pieces.
Your aunt returns to the call with your mom, fills in her missing pieces.
Your mom returns to the call with you and has the entire recipe in tact.
Each time someone in this chain was put on hold, they remained in waiting, until all the subsequent calls were completed and the information came back through the chain. Similar to recursive functions, every time the function is called the previous function is put on hold. Once the base case is met (in this example, once the recipe is complete) the data (or ingredients) move back through the stack completing each function call.
The a-ha function!!
Ok, here it is. This function serves no other purpose than to show you how recursion works. It’s a simple function that serves to print out the variable
number to illustrate how recursion works.
- We call the function with 1 —
- The first if statement is our base case — which ensures that we don’t end up in an infinite loop — this will stop the recursion once the function is called with the number variable equal to 7
- Then we print out the number variable before we call the recursion function again, passing
number + 1as the new input
- Finally, we print the number again before we finish the function
The output from this function will be;
As you’ll see, the initial call to the recursion function is on line 11 and we pass in an input of 1. Since 1 does not equal 7, we enter the else portion of the if statement. The output shows that
in: 1 is followed by
in: 2 which means, that once we call line 6
recursion(number + 1) we’ve entered the recursive process. The first function, which has the number variable equal to 1 is the last to print it’s
out: 1 line. This is known as first in last out.
Remember our recipe phone chain? The last person to be contacted, your great-aunt, was the first person to hang up the phone. The first person to make the call — you — hung up the phone last.
How is recursion useful?
Well, this might be debatable. Some programmers choose iteration instead of using recursion to solve problems. This is, in part, due to the high cost recursion comes with. The computer is keeping track of every function call, which is why that base case is so important. In my previous example, if I didn’t have a base case:
if (number == 7) then line 6:
recursion(number + 1) would just keep going and going. This would result in the error
Maximum call stack size exceeded which means your recursive function will be called an infinite number of times. But, ultimately, recursion is good to know. If the problem is simple enough, recursion can be the better option.
The Fibonacci numbers, beginning with 1, are the result of adding the first two numbers preceding.
1+1=2 | 2+1=3 | 3+2=5 | 5+3=8 | …etc.
Resulting in the chain:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144….
Recursively, that would look like…
So if we called
fibonacci(8) we would get the 8th number in the line of numbers, which is 21.
Since I love printing out my data to see exactly what I’m manipulating, below is a helpful example.
I’ve added an input to my fibonacci function this time, called
which to keep track of which stack we are in. On line 13 I call
fibonacci(6) which produces the output;
n is 6 in -a
n is 5 in ---b
n is 4 in ---b
n is 3 in ---b
n is 3 in -----c
n is 4 in -----c
n is 3 in ---b
You’ll see seven lines of output because the first number 1 in the sequence is added to 0 to produce the second number 1, so the 6th number in the sequence is 8, which is the correct output at the bottom. You’ll also see the order of stack calls as we print out a different
which value for each recursive call.
The next problem — factorials — often represented by
n! is the output of
n multiplied by every positive number that is less than
5! would be the product of
5 x 4 x 3 x 2 x 1 and recursively that would look like…
Again, if we print out
n along the way, we can see how we’re manipulating the data. So, the same code with some console.logs is…
And that output would look like…
Once we get down to
n = 1 it returns 1 as it does not pass the if statement. Then the program makes it’s way back through the stack, multiplying 1 x 2 x 3 x 4…etc. You can see the correct products along the way from line 7,
console.log("out: ", result)
It’s ok if you don’t get it!
This concept is abstract and can often be hard to grasp. Even after my major a-ha moment, even after explaining the concept of recursion to students multiple times, I still struggle with recursion myself. Unlike computers, it’s difficult for the brain to store that much information quickly and correctly, so we can’t visualize recursion. This is why printing out my variables along the recursive path has helped me so much. I hope it has helped you, too!