Recursion – It’s Not a Hallucination

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

    The Big O

    First off, this is a technical blog. My apologies if you came here looking for something a little sexier. Not that Big O Notation can’t be sexy. Depends on what floats your boat or sinks your battleship. Anywho, the following is a little teaser on Big O.

    Foreplay

    When you take your first few steps learning how to program, something like Big O Notation is the furthest thing from your mind. Learning to code is hard. Period. There is so much to know, and quite frankly, it is daunting. Imagine looking up at the highest peaks of Mt. Everest from the bottom of the mountain. Now imagine that the mountain is always shifting and getting bigger. That’s what it feels like when you start learning. Somewhere along the way (hopefully), your footing will become more secure on the shifting ground and you’ll gain some comfortability in the place of not knowing. Because nobody knows it all. Keep one foot in front of the other and keep climbing. Try to enjoy the ride.

    If you went to a bootcamp, there was so much knowledge being pushed into your brain in a few short months. Bootcamps are great, but they just focus on web development. When you graduate and start to prepare for interviews, you begin to hear scary terms that you never heard before. Things like Linked Lists, Big O Notation, Bitwise Operators, Binary Trees, Stacks, Queues, etc. These are all computer science topics and good to know, but unless you are working on high level stuff, you probably don’t have to know all of them. But those pesky interviewers will probably test you on them because they know most bootcamps don’t teach it and because they had to learn it when they got their BS in CS.

    Heavy Petting

    One of those terms, Big O Notation, is actually very useful to know. When you begin to program, you’re not thinking about how your program will scale if a few thousand or perhaps a million people start to use it. You just learn what a for loop is, then learn you can have nested for loops, and you think everything is grand! Not so fast Kemosabe. This is where Big O Notation and scaling come in. Let’s take a look at how you might write a function to double each element in an array of arrays.

    
    function doubleMe(arrayOfArrays) {
      const doubledArrayOfArrays = [];
    
      for (let i = 0; i < arrayOfArrays.length; i++) {
        let placeholderArray = []
        for (let j = 0; j < arrayOfArrays[i].length; j++) {
          placeholderArray.push(arrayOfArrays[i][j] * 2);
        }
        doubledArrayOfArrays.push(placeholderArray)
      }
    
     return doubledArrayOfArrays;
    }
    
    doubleMe([[1,2,3], [4,5,6], [7,8,9]];  // [[2,4,6], [8,10,12], [14,16,18]]
    
    

    This might look all fine and dandy, and when you first learn about nested for loops they might seem like the best thing since sliced bread! But let’s take a look at how this will scale.

    We Have Lift Off

    The length or size of our arrayOfArrays above is 3. However, since each element of the array is another array the function has to work that much more. Basically, for every item in the array (n for the input size), we have to do n more operations. So n * n == n^2 or O(n^2). The given example might be a little too on the nose being 3^2 is 9. It’s usually not that exact. You might ask, ‘So what’s the big deal? The function only has to run 9 times instead of 3’. Well, everything is groovy if the input is low, but what if it grows to 100 or 1,000 or 1,000,000. You start to get the point. With lower inputs, it’s not a big deal, but as the input grows, so does the time complexity of the function.

    BigOn2

    Weeeeeeeeeeeeeeeee!!!!

    I’m Very Sensitive

    Sorry if I got a little too excited. Let’s back up here a bit. Maybe I should start with O(1). Gayle Laakmann McDowell, author of a Cracking the Coding Interview, has a great video about Big O. It’s definitely worth a watch. She gives a great example about a problem South African programmers were having. Their internet connection was super slow and it was taking a long time to transfer data to team members in a different city. So they tried an experiment. They transferred the data to a usb drive and had a carrier pigeon (let’s call him Bob) deliver it to their work mates in the other city. At the same time they were transferring the data through their internet connection. The race between Bob and the internet. Guess who won?

    If you said ‘BOB!’, then you are correct. So what does this have to do with Big O? Glad you asked! Bob’s flight in Big O terms is O(1). If it took Bob 30 minutes to get from one office to the other, then no matter what size the file is, it does not change the amount of time it takes him. Whether he’s flying with 10MB or 1TB, it still takes him 30 minutes. So O(1) is a program or function that takes the same amount of time to run no matter how large the input grows.

    Time_Complexity

    Bob is a low flying bird

    Almost There

    Revisiting our South African friends, as the size of the data they were transferring (over the internet) grew, the time it took to transfer grew by the same order. This would be O(n) and is linear in time and space. The green line in the graph above represents this. What would this look like as a function? Take my hand and let us find out.

    
    function tripleMe(array) {
      const tripledArray = [];
    
      for (let i = 0; i < array.length; i++) {
        tripledArray.push(array[i] * 3);
      }
    
      return tripledArray;
    }
    
    tripleMe([1,2,3,4,5]);   // [3,6,9,12,15]
    
    

    Each element of the array gets worked on once. If our array had 1,000,000 elements, our for loop would run 1,000,000 times. From an input of an array of 1 element to an input of an array with 1,000,000 elements, the time complexity a straight line.

    Pillow Talk

    There are definitely other elements of Big O to talk about and understand, but I’m spent. I gave a pretty good (in my humble opinion) performance overview of the basics. I hope it was as good for you as it was for me. Sweet dreams buttercup.