Recursive Functions

Dear JScripter,

If you are seeing this letter, then it means it is time to finally understand the legend of Recursive functions as used in the language you’ve been toiling to understand better. If you’ve cared enough to look for answers to the myth of Recursion...


Excuse me, I finally watched Troy (yeah the one that came out in 2004) so I’m pretty still in the moment. Why did Hector have to die?! Then the people of Troy had their walls breached?! Sad. Great movie (still didn’t stop me from deleting it out of pain). Anyway, back to business!

We have a long journey to go in this article if we are going to fully understand Recursive Functions. Longer now that I took a detour to Troy.

What are Recursive Functions?

A Recursive Function is a function that recalls itself simply put. It’s like wanting to run a piece of code or expression over and over again without using the traditional looping methods such as, for loops, while loops, forIn, forEach, etc. Now that you know what it is, let’s go on to see it in action. For our first example, we will try to make the browser console say “Hi” to us five times. Let’s use a for loop then a recursive function because I’m pretty sure you must be wondering what the difference between both is. For the For-Loop:

for (let index = 0; index < 5; index++) {
    console.log("Hi");
}

Here, we have a for loop that we’ve used to greet us five times. Below is the output:
for-hi.png

Seems ok? Let’s use a Recursive Function for the same task:

function num(n){
    if(n >= 1){
        console.log("Hi");
        return num(n-1);    
    } 
}

num(5);

That’s the code, now for its output:

recur-hi.png

So what? Well, before I get on to explain the piece of recursive code, I want you to observe the difference in the output of both pieces of code. The for-loop is clearly rude and if the King of Greece during that Trojan war period were to be reading this, he would have it beheaded. What it basically did was stare lazily after being ordered to greet us five times, then proceed to say: “Hi five times”. What insolence?! Then there is the Recursive Function, a piece of code with proper upbringing, it said “hi” and it did it five times. It’s not like the for loop did not run 5 times but you know how human perception is Pay close attention, we are about to find out what happens with Recursive Functions. Each line of code is labeled:

function num(n) { // ----------- 1
    if (n >= 1) { // ----------- 2
        console.log("Hi"); // --------- 3
        return num(n-1);   // --------- 4 
    } 
}

num(5);

Above, is the piece of code again.

  1. A Function named num() that expects an argument or a parameter(or variable sorta) was created.
  2. A condition to test if n is greater or equal to 1 is set. That condition serves as a wrapper for the entire body of expression in the function.
  3. We log “hi” into the console. In other words, making our program say “hi”.
  4. Now, this is the most important part of the program. This is where we make our code run as much as we want. We ask the function to return itself – num(), but then decrement by 1 every time it calls itself num(n-1); Let me rephrase (4): What we do with that expression is simply ask the function to run itself repeatedly but each time it does that, it should do it with a new value of n that’s been decremented. The reason for the decrementing is so that ‘n’ can reduce to the value at which we’ve set our condition (the if statement). If n isn’t decremented, our function will run infinitely and you will get a call stack error. You could try! If you get curious as I do, you’d be wondering, “Does that not mean it should greet us a new ‘n-1’ times”? No is the answer. This would be clearer to you with a description of what goes down… eh no, not in the DMs, but in the call stack!

A Deeper Understanding.

To digress a bit, when you run a JS program you’ve just written, something called the call stack holds a reference to all the functions in your code. If you’ve not wrapped your expressions in functions, it does it at runtime. It does so, to remember what it should be doing in a specific moment and what it was doing at that moment. The functions are listed in a FIFO manner, First in, First Out. This means the first function in the call stack is the first function to get dealt with and popped off the stack. You can read up on the JS stack if this bit confuses you.

What happens in the Stack when we run the code?

  1. For Loop

for-stack.png

Note the part in the picture highlighted yellow and labeled call stack. That is well, our stack. The part highlighted green denotes the content of the stack at a point in time. When the code on the left is run, an anonymous function gets into the stack and runs five times as specified in the for-loop. The point here is that the function is called just once but the code in it, runs five times.

  1. The Recursive Function

recur-stack0.png

This is the output of the recursive function at first when it is run. At this point, the code is checking the ‘if’ condition. If you look at the stack you’d see an anonymous function which is like this big wrapper that activates things. You then have the ‘num’ function in the call stack, highlighted green. Also, at this point, ‘n' is still equal to 5’. When the function runs to the point where our ‘if’ condition fails, the image below is what the stack looks like.

recur-stack0.png

If you count the number of ‘num’ function calls on the stack, you’d see it’s up to six. I’ve highlighted some blue and another green. The green one has an arrow next to it. That arrow indicates what the call stack is currently busy doing. Each ‘num’ function on the call stack is proportional to the number of times the console will say ‘hi’ to us. You might wonder why six? The sixth one highlighted green is the initial call. It is what got things swinging. In the former image, you would notice that ‘n’ was still equal to 5 and now ‘n’ is equal to 0. So a recursive function in a way creates instances of itself so to speak (functions are first-class objects so instance seems like the right word), into the call stack. As the code continues to run, you’ll see the functions leaving the call stack one by one in a FIFO order. The result of each exit being the ‘hi’ logged into the console.

Two things are important when creating a recursive function.

  1. A condition – which helps to set an endpoint for function call. This is necessary to avoid exceeding the maximum call stack size (a fancy phrase that means you’ve packed too many functions into the call stack).
  2. A decrementing expression or an incrementing one (it all depends on your condition). This is the brain behind the magic that makes the function call itself repeatedly.

For-Loops or Recursive functions?

When it comes to performance, For-loops are absolutely better. There are no multiple function calls so your call stack is clean and does less. When it comes to implementing mathematical formulas though, using the Recursive Method has an aesthetic similarity to the real thing in most cases. Let me end this article by dropping a recursive function exponent function.

function power(base, exponent) {
    if (exponent == 0) {
        return 1;
    } else {
        return base * power(base, exponent - 1);
    }
}

console.log(power(2, 4));

The above code was copied from Eloquent JavaScript by Marijn Haverbeke

No Comments Yet

Add a comment