Does recursion scare the crap out you? Well, it should! You should stop reading this now, draw the blinds, get in bed and pull the covers over your head. Just kidding! Recursion is pretty cool once you get the hang of it. I’m going to try to break it down for you so you won’t have to run and hide every time it’s mentioned.

From Wikipedia:

Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem (as opposed to iteration). The approach can be applied to many types of problems, and recursion is one of the central ideas of computer science.

Okay, so basically it is a problem that can be broken down into smaller versions of itself. This happens when a function gets called repeatedly by itself until it reaches the stopping point, which is called the base case. So a recursive function is a function that calls itself. Every time the function calls itself, it is looking for the base case. If the base case is not found, the function calls itself again. If you think about it too long, it might make you feel like you’re hallucinating. And down the rabbit hole we go…

Think of it like a for loop, except that the function is sort of flying blind until it reaches the base case.

Enough talk, let’s see an example.

function multiplyUpToFive() {
  // (1 * 2 * 3 * 4) * 5 or
  return multiplyUpToFour() * 5;
}

function multiplyUpToFour() {
  // (1 * 2 * 3) * 4 or
  return multiplyUpToThree() * 4;
}
// and down to multiplyUpToOne()

What we’re doing here is breaking down the problem into smaller problems. That wasn’t a recursive function, but it acts the same way a recursive function does. I’ll rectify this further on. Now for our recursive function, by taking function called multiplyUpTo(n), you can say that the definition of the function is equal to taking the product of

  • the products up to n – 1
  • times n
  • Let’s see…

    function multiplyUpTo(n) {
      return multiplyUpTo(n - 1) * n;
    }
    
    // let's call this with an argument of 4 and see what happens
    
    multiplyUpTo(4)
    multiplyUpTo(3)  // gets called
    multiplyUpTo(2)  // gets called
    multiplyUpTo(1)  // gets called
    multiplyUpTo(0)  // gets called
    multiplyUpTo(-1) // gets called
    // shiiiiiit. Looks like we might be stuck in a recursive loop forever!!!
    

    That function would have ran infinitely because we didn’t add a base case. Think of the base case as the roof of the function. Without it the function will keep going out into space – to infinity and beyond! There’s literally nothing to stop it. Okay, enough analogies. Let’s fix our multiplier function.

    function multiplyUpTo(n) {
      // Our base case is 1, so we'll check if n equals 1
      if (n == 1) {
        return 1;
      }
    
      return multiplyUpTo(n - 1) * n;
    }
    
    // Now if we call our function with 4 as the argument, this is what will happen
    
    multiplyUpTo(4)
    // n does not equal 1, so it's called again
    multiplyUpTo(3) * 4
    // Again n does not equal 1
    multiplyUpTo(2) * 3
    multiplyUpTo(1) * 2
    
    // We reached our base case which is 1 and our function will not repeat forever 

    Now our function knows where it is in the universe and has found its purpose in life.

    Okay, the function has purpose. Now what?

    // Once the function reaches the base case, it will now solve all of the
    // problems it left behind
    
    multiplyUpTo(1) * 2 // 1 * 2 = 2
    multiplyUpTo(2) * 3 // 2 * 3 = 6
    multiplyUpTo(3) * 4 // 6 * 4 = 24
    
    // Once the function has an answer to all of itselves (I think I made that up),
    // then it returns the product the original function call. Woah dude.
    

    If we’re feeling good about our JavaScript we can even use a ternary statement to really make our function compact.

    function multiplyUpTo(n) {
      return n == 1 ? 1 : multiplyUpTo(n - 1) * n;
    }
    

    I like it! Thinking recursively makes you think recursively makes you think recursively. See what I did there. Yeah, I’m a dork. Hopefully this helped you understand the world of recursion. It’s quite fun to write algorithms this way. Although it might be scary at first, don’t worry: The worst that can happen is you float away into the infinite:)

    Advertisements

    Leave a Reply

    Fill in your details below or click an icon to log in:

    WordPress.com Logo

    You are commenting using your WordPress.com account. Log Out / Change )

    Twitter picture

    You are commenting using your Twitter account. Log Out / Change )

    Facebook photo

    You are commenting using your Facebook account. Log Out / Change )

    Google+ photo

    You are commenting using your Google+ account. Log Out / Change )

    Connecting to %s