Recursion with JavaScript Pt. 1

Recursion is a programming concept (definitely not limited to JavaScript) where a function calls itself within itself (<==lol wtf?). I think of it as the ultimate loop. You have your for, while, and for in loops, but recursive algorithms are the big looping kahuna.

Most use factorials as an example of basic recursion. So let's do it! Write a function takes a number n and then calculates its factorial: 1 * 2 * 3...all the way to n.

var factorial = fuction(num) {
	if (num < 0) {
    	return -1;
    } else if (num===0) {
    	return 1;
    } else {
    	return num * factorial(num-1);
    }
};

When to Use Recursion

Recursion should be reserved for more complex or difficult problems that can be broken down into smaller versions of itself. If by solving a smaller version of the problem itself, then you can build it up into a solution for the entire problem.

If you can apply the same algorithm to each smaller piece and combine the results, you have a good case for using recursion.

Some examples include finding permutations of a set of choices, traversing through data structures, and various sorting methods. Factorials are a great, basic recursion problem.

Tackling Recursion

What really helped me was breaking recursion down into several parts:

  • the base case
  • the recursive/general case

Base Case:

The base case is the part of the function that stops the recursion. It's generally something we already know the answer to, so it can be met without making any more recursive calls.

Without a base case, your recurse function will continue forever and you will break the internet.

In the factorial code above, I have two base cases.

if (num < 0) {
    	return -1;
    } else if (num===0) {
    	return 1;
    }

This covers both edge cases (where if the initial number inputted is negative or 0) and also ensures that when the number we recurse reaches 0, we get out of the recursive function.

The Recursive Case:

The recursive (or general) case is where the magic happens. This is where we feed the problem back into itself, where the function calls itself. I like to think of it as creating several parallel universes, which all come together in the end (when they meet the base case).

In the factorial code above, I have my recursive case:

else {
    	return num * factorial(num-1);
    }

With this, you're effectively left with a chain of num from all the recursions that the problem goes through.

Revisiting the Factorial Example

Let's go through this again!

var factorial = fuction(num) {
	if (num < 0) {
    	return -1;
    } else if (num===0) {
    	return 1;
    } else {
    	return num * factorial(num-1);
    }
};

We will use 4 as our num:

factorial(4);

Round 1:
The first time through the function (with num=4), we go to the else and our current result is 4 * factorial(4-1). This isn't returned yet though, because the function is still active. We have not yet reached our base case. Now we do the same thing over but with num = 3.

Round 2:
Taking 3 through factorial, we again skip straight to the else and add 3 to our result in round 1: 4 * 3 * factorial(3-1). Again, no returning because our function is still alive.

Round 3:
Again through factorial with num=2. Because 2 is not less than 0 or 0, we skip right to the else and add to our result: 4 * 3 * 2 * factorial(2-1). We're getting somewhere soon!

Round 4:

 factorial (1); 

adds to our result: 4 * 3 * 2 * 1 * factorial(0).
Now, we could have added an else if statement to our function like... else if (num ===1) { return 1} or modified our existing else if statement to return if num===0 || num===1. Either of those are fine. What matters though, is that they return you out of the recursion.

Round 5 & Result:

factorial(0)
``` returns 1 and we finally break out of our recursion! Now our full results are returned: ```4 * 3 * 2 * 1 * 1```, which gives us a product of 24.

###More Advanced Recursion Problems
Here are just a few examples of recursion problems. 

* Binary search
* Merge sort
* Generate every permutation of an <i>n</i>-round game of rock, paper, scissors.
* <a href="http://www.math.utah.edu/~alfeld/queens/queens.html" target="_blank">N-queens</a>

I'll go over Rock, Paper, Scissors in Pt 2. That one's...fun.

Resources:

<a href="http://www.codecademy.com/courses/javascript-lesson-205/0/1" target="_blank">Codecademy's Recursion Course</a> - This was a great start for me and my launchpad to more advanced recursion techniques. It was a little slow for me and it also covered only the basics.<br>
<a href="http://www.sparknotes.com/cs/recursion/whatisrecursion/section1.rhtml" target="_blank">Spark Notes' Recursion</a> - Goes into more detail than Codecademy. Highly recommend reading this.