What is Recursion? (Computer Science theory)

Recursion and loops can almost be used interchangeably. Not only can you do the same thing, but loops are easier to read and have a faster time complexity. So what is the point of recursion? 95% of the time, the answer is nothing. That is not the point though. The point is that understanding recursion will make you a better programmer. Once you get familiar with what is going on “underneath the hood”, your possibilities expand and your problem solving abilities increase.

So what is recursion exactly? Recursion is when a function calls itself until a repeated task is completed. Every recursive function must have at least one base case, and something that makes progress towards that base case. If you don’t have either of these things, you will have an infinite loop.

Here is a basic example of recursion using JavaScript:

function countDown(num) {
  if (num === 0) {
    return;
  }
  console.log(num);
  countDown(num - 1);
}
countDown(5);

A breakdown of the recursive function above:

1. First a function named countDown is created, while passing in a parameter of num .
2. Inside of the function is a simple if statement. inside of the if statement it says: if the number that we passed in is equal to 0, then return out of the function.
3. If the if statement is false, it will skip over it and proceed to whats underneath it. We are going to console.log() the number that we are passing in.
4. Then we are going to call the exact function that we are inside. But this time we are going to call it with the number that we passed in, minus one. This function will then call itself until the number is 0.

So when countDown(5) is called, we will see (5, 4, 3, 2, 1) in the console.

This function has everything needed to be a recursive function. It has a base case, which is whats inside the if statement. As well as progress being made towards that base case, which is when we call the same function, but instead it is called with minus-ing 1 to the initial value.

Here is a slightly more complex example of recursion:

function pow(x, n) {
  if (n == 1) {
    return x;
  }
  return x * pow(x, n - 1);
}

pow(2, 3);

Lets break this down:

1. First we declare a function named pow that takes 2 parameters (x, n) . x is the number that we want to multiply. n is the power^ that we want to multiply it by.
2. inside of the pow(x, n) function, there is an if statement. The if statement says: if n is equal to one, then step inside of the if brackets
3. Inside of those brackets, we just want to return the value of x. (This is the base case)
4. If n does not equal one then I want to skip the if statement. The rest of the code says: return x multiplied by calling the function again (pow(x, n - 1)), but instead we minus one from n. Now this is where the tricky part begins. What this causes, is called a “stack”.

When we say: return x * pow(x, n - 1); , we are calling the function again while minus-ing 1 from n, this got pushed onto the “stack” because the computer does not have the final value of n yet. So then the function gets called again with the new value of n being 2. Then the process above keeps happening (getting pushed to the stack) until we hit the base case (which in this case it is when n === 1). Once the base case is hit, the computer will have an “aha” moment. It now knows what that return value is. Once the computer has the final value (in this case it is 2), it will replace “pow(x, n - 1);” in all instances of the function getting recalled to “2”. So the computer is doing 2 * 2 * 2 , which is 8.

Here is an amazing video from Computerphile that explains the “stack”. This is a visual representation, so it may be easier to understand and learn from it.

When should you use recursion?

Recursion does have advantages over iteration, one of those being ; when an iterative approach is too complex. For example, when you are trying to traverse a file system. You start at the root folder, and then search from its children. Then within that file you search from its children, and so on. Recursion in this example, allows you to search multiple branches without having to check many conditions.

Recursion does have its place. Although it isn’t many, they do exist. Developers are very opinionated about recursion. You will hear that some developers love it and use it everywhere, others have the opposite opinion. Recursion can replace almost all iterative approaches.

Now that you understand recursion it up to you to decide whether you should use it or not.