My Time Spent In Recursionville

If there's one thing that gets the rusty gears in my brain turning when it comes to programming principles, by golly, let me tell you, it is recursion! When I first learned about the concept of recursion, I felt like there was NO way I was ever going to figure what in the heck people meant when they said that. Granted, the Google easter egg of displaying "Did you mean recursion?" when you type it into the search sort of helped to solidify the general idea of what it meant, but still, recursion is one of the more tricky concepts to wrap one's head around.

I'll be attempting to simplify some of the core concepts of what recursion actually means, the two main types of recursion and giving some insight on things that made it easier for me to understand just exactly what the heck is going on. Let's dive in with some examples!

I'm going to start off by presenting the example given in Free Code Camp's curriculum for JavaScript Data Structures and Algorithms module: Replace Loops using Recursion

function multiply(arr, n) {
    if (n <= 0) {
      return 1;
    } else {
      return multiply(arr, n - 1) * arr[n - 1];
    }
  }

Here, we're given a function that contains two parameters: one for arr and the other n. One can infer that arr is for passing in an array and n is for the number of elements within said array.

if (n <= 0) {
      return 1;
    } 

An essential component to any recursive function is what's known as the "base case". I like to think of this as something similar to the conditional statement found within a for loop, usually located within the middle of the statements in the parentheses. The base case basically acts as a breaking point within the recursive function so that the function doesn't keep calling itself into oblivion (the dreaded infinite loop aaaahhhhhh!!!!). We'll later see what the return 1 component is used for.

else {
      return multiply(arr, n - 1) * arr[n - 1];
    }

And finally, we've reached our recursive call, where all of the magic happens. I'd just like to point out what the reason for having the n - 1 and arr[n - 1] is; this part confused the heck out of me for a while!

The reason for subtracting n by 1 in the function's argument is that this will form the next recursive function's argument where n is decremented again and again until we reach the base case.

The reason the arr[n - 1] index is subtracted by n - 1 is that this expression acts as the iterator that will be sorting through the arrays for us; i.e., arr[2], then arr[1] and so on. We're subtracting n by 1 to match the zero-based indexing that arrays use.

Let's call in some actual arguments to our function and get going!

function multiply(arr, n) {
    if (n <= 0) {
      return 1;
    } else {
      return multiply(arr, n - 1) * arr[n - 1];
    }
  }

multiply([1, 2, 3], 3);

The function call gets invoked and JavaScript opens up an execution context for the function multiply and assigns in local memory the variable arr to [1, 2, 3] and n to 3. JS checks the conditional statement if (n <= 0) and that is false, since n = 3. So it gets skipped over and we enter our else statement.

 else {
      return multiply([1, 2, 3], 3 - 1) * arr[n - 1];
    }

Once we see to return multiply([1, 2, 3], 3 - 1), n gets reassigned to 2 and the code in arr[n - 1] doesn't get evaluated, since the return statement for return multiply([1, 2, 3], 2) is unknown. So now it's time to open another execution context with the arguments:

multiply([1, 2, 3], 2)

We repeat basically the same process as previously; arr is still equal to [1, 2, 3] and n is now equal to 2. Is if (n <= 0) true?

Nope! So we continue on to our else statement and see that:

else {
      return multiply([1, 2, 3], 2 - 1) * arr[n - 1];
    }

n is now equal to 1

And since we're returning yet another recursive statement, we're going to enter another execution context where n = 1:

function multiply([1, 2, 3], 1) {
    if (1 <= 0) {
      return 1;
    } else {
      return multiply(arr, 1 - 1) * arr[n - 1];
    }
  }

And again, since 1 <= 0 is false we're going to enter yet another execution context! Only this time, something is different; n = 0! So our if statement is true and thus, we are able to return 1

function multiply([1, 2, 3], 0) {
    if (0 <= 0) {
      return 1;
    } else {    //we don't enter the else statement!
      return multiply(arr, n - 1) * arr[n - 1];
    }
  }

Now something very important happens. We never enter the else statement in our recursive function where n = 0. We return 1 and the return value for that function call is 1! 1 gets returned to it's calling-function's origin where n = 1. So we do some garbage collecting for our function call where n = 0 and return 1 to our previously called function. Here's what it looks like:

function multiply([1, 2, 3], 1) {
    if (1 <= 0) {
      return 1;
    } else {
      return multiply([1, 2, 3], 1 - 1) * arr[1 - 1];  

    }
  }

turns into...

function multiply([1, 2, 3], 1) {
    if (1 <= 0) {
      return 1;
    } else {
      return 1 * arr[0];                                  
    }
  }

Our recursive call after the else statement gets evaluated to 1 because the function call we made previously where n = 0 returned 1, thus, that is how 1 is the substituted value where our previous function call was. I hope that makes sense! That's a very important concept to learn. It's hard to wrap your head around how a function call that looks like multiply([1,2,3], 1- 1) can evaluate to 1! But it makes sense when you think about it (I hope!).

So now we can return our second value where 1 * arr[0], which is in fact 1 * 1. This gives us 1 and we'll use that as the return value to the calling function where n = 2:

 function multiply([1, 2, 3], 2) {
    if (2 <= 0) {
      return 1;
    } else {
      return 2 - 1 * arr[2 - 1];  //evaluates to arr[1]
    }
  }

Are you beginning to see how this works? The return value from this function call is going to be equal to 1 * arr[1], which is 1 * 2. That equals 2! So our return value to our next function call where n = 3 is going to equal 2:

 function multiply([1, 2, 3], 3) {
    if (3 <= 0) {
      return 1;
    } else {
      return 3 - 1 * arr[3 - 1];  //evaluates to arr[2]
    }
  }

And this evaluates to...

 function multiply([1, 2, 3], 2) {
    if (1 <= 0) {
      return 1;
    } else {
      return 2 * arr[2]  
    }
  }

Which returns 2 * 3 and that equals 6, which is our final returned value! Essentially, we've performed the action of 1 * 2 * 3, but by using recursion to do so. Whew! That's a lot of work just to do a simple expression, isn't it?

This particular form of recursion is known as linear recursion. It is known as linear, because it keeps calling a function over and over until the base case is met, and then returns all of the values it gets to the previous function that called it. You can think of it like a straight line that goes down and then once it reaches the base case, it goes back the way it came, in the opposite direction.

I'm not going to explain it in this article (possibly a later one), but another type of recursion is known as tail recursion (or tail-end recursion). If you'd like me to write another article on that and you found this one helpful, please let me know! I'm still a n00b, but am trying my best to explain these things in ways that make sense to me. Let me know how I can improve!

Thank you for your time and I hope you found this worth your while
<3