This is a standing joke at most engineering schools and it explains what it is in a very short way. Recursion is a mathematical concept. Let's explain it a bit more. The official definition says the following:

Ok, what does that mean in human speak? It says that at some point in running our function, we will call ourselves. This means we have a function that looks something like this:

function something() {
  statement;
  statement;
  if(condition) {
    something();
  }
  return someValue;
}

We can see that the function something() at some point in its body calls itself. A recursive function should abide to the following rules:

• Should call itself
• Should eventually meet an exit condition

If a recursive function doesn't have an exit condition, we will run out of memory as the function will call itself for all eternity. There are certain types of problems that are more suitable than others to apply recursive programming to. Examples of these are:

• Traversing trees
• Compiling code
• Writing algorithms for compression
• Sort lists

There are many more examples, but it's important to remember that, although it's a great tool, it shouldn't be used everywhere. Let's look at an example where recursion really shines. Our example is a linked list. A linked list consists of nodes that know about the node they are connected to. The code for the Node structure looks like this:

class Node {
  constructor(
    public left, 
    public value
  ) {}
}

Using such a structure as a Node, we can construct a linked list consisting of several linked nodes. We can connect a set of node instances in the following way:

const head = new Node(null, 1);
const firstNode = new Node(head, 2);
const secondNode = new Node(firstNode, 3);

A graphical representation of the preceding code would be the following diagram. Here, we can clearly see what our nodes consist of and how they are connected:

Here, we have a linked list where we have three connected node instances. The head node is not connected to the node to the left. The second node however is connected to the first node and the first node is connected to the head node. The following type of operations on a list might be interesting to do:

• Find the head node, given any node in the list
• Insert a node at a given point in the list
• Remove a node from a given point in the list

Let's have a look at how we can solve the first bullet point. Firstly, we will use an imperative approach and thereafter we will use a recursive approach to see how they differ. More importantly, let's discuss why the recursive approach might be preferred:

// demo of how to find the head node, imperative style

const head = new Node(null, 1);
const firstNode = new Node(head, 2);
const secondNode = new Node(firstNode, 3); 

function findHeadImperative (startNode)  {
  while (startNode.left !== null) {
    startNode = startNode.left;
  }
  return startNode;
}

const foundImp = findHeadImperative(secondNode);
console.log('found', foundImp);
console.log(foundImp === head);

As we can see here, we are using a while loop to traverse through the list until we find the node instance whose left property is null. Now, let's show the recursive approach:

// demo of how to find head node, declarative style using recursion

const head = new Node(null, 1);
const firstNode = new Node(head, 2);
const secondNode = new Node(firstNode, 3); 

function findHeadRecursive(startNode) {
  if(startNode.left !== null) {
    return findHeadRecursive(startNode.left);
  } else {
    return startNode;
  }
}

const found = findHeadRecursive(secondNode);
console.log('found', found);
console.log(found === head);

In the preceding code, we check whether startNode.left is null. If that is the case, we have reached our exit condition. If we haven't reached the exit condition yet, we keep on calling ourselves.

Ok, so we have an imperative approach and a recursive approach. Why is the latter so much better? Well, with the recursive approach, we start off with a long list and we make the list shorter every time we call ourselves: a bit of a divide and conquer approach. One thing that clearly stands out with the recursive approach is that we defer execution by saying, no, our exit condition isn't met yet, keep processing. Keep processing means we call ourselves as we do in our if clause. Is the point of recursive programming that we get fewer lines of code? Well, that could be the result, but more importantly: it changes our mindset toward how we go about solving problems. In imperative programming, we have a let's solve the problem from top to bottom mindset, whereas in recursive programming, our mindset is more, define when we are done and slice down the problem to make it easier to deal with. In the preceding case, we discarded the part of our linked list that wasn't interesting anymore.