While learning how to program, recursion was the most difficult programming concept I encountered because not only does it seem cryptic, it seems like a leaky abstraction. You can barely gain a mental picture of how it works and when to make use of it simply by reading its definition or by merely examining how it is used.

The most common definition of recursion, “a function that calls itself”, even leads to more confusion especially when you are still in your early career learning how to code. You would most likely be curious to know its usefulness and when to make use of this programming construct.

This article will attempt to explain the following:

• How recursion works

• When to use recursion

How recursion works

The secret to understanding and mastering recursion lies in its semantics (the meaning of its syntax and the underlying concepts) and how it works under the hood (what happens in the execution or runtime environment).

Recursion Semantics

There are two main concepts in recursion:

1. The base case

2. The recursive case

The base case is what terminates the loop in a recursion. Somewhat similar to the boolean expression that should return false in a for-loop so as to terminate the looping operation. Similar to the boolean expression in a for-loop, which could be a compound boolean expression (an expression that is comprised of smaller, simpler, boolean expressions, e.g false || (true && true)), there could be one or more base cases in a recursion. The number of base cases depends on the requirement of the problem at hand. We will use the sum of an array exercise below to demonstrate this.

The recursive case is the part of a recursion that calls itself but usually with different arguments down the line. Similar to the base case, there could be one or more recursive cases which also depends on the requirements of the problem. Now, here comes the magic of recursion in my opinion. The recursive case has three parts that when understood, can make you a recursion guru 😎.

• Pre-recurse (before the recursive call)

• Recursive call

• Post-recurse (after the recursive call)

Let us demonstrate these concepts by solving a simple exercise. The sum of elements of an array.

Please run these code blocks in the console on your computer or on a playground like jsbin.com to follow along and see the behaviour of the code.

const numbers = [1, 2, 3, 4, 5];

function sum(arr) {
  // base case
  if (arr.length === 0) {
    return 0;
  }
  // pre recurse
  let head = arr.shift();
  // recursive case
  return head + sum(arr) // recursive call;
  // post recurse
}

console.log(sum(numbers));

This example is merely illustrative. It is neither an ideal nor performant solution.

When we run the code, we get the sum of the elements of the array.

We have not made use of the post-recurse phase of the recursion yet but we will do so shortly to demonstrate what happens in the execution environment when the sum function is called.

What happens in the execution/runtime environment when the sum function is called.

Most programming languages use a stack data structure to maintain the order of function executions in their programs. This facility is called a call stack. You can think of a stack data structure as an array with only a push and pop operation. You can’t do nothing else with it. In order words, you can only remove what was last added to the array (with the push operation).

With a call stack, every function call pushes a stack frame into the call stack. Think of a stack frame as a local execution context or local function scope.

The call stack manages three states when creating or adding more stack frames; the return address, the return value and the function argument.

The following steps illustrate how the states are managed:

• When the sum function is called the first time, a stack frame is added to the call stack with the function argument as the numbers array, the return address as the call stack and the return value as 1 + (the return value of the recursive call). The return value here is the expression after the second return keyword; head + sum(arr). Bear in mind that we are mutating the numbers array each time by removing the first element of the array before evoking the recursive call. This is denoted by arr.shift().

  

• When the sum function is called the second time, another stack frame is added to the call stack and the return address is the stack frame beneath it (the sum1 quadrant by the bottom-left in the image above). The return value is 2 + the return value of the next recursive call while the function argument is the array containing 2, 3 since the array has been mutated to exclude 1.

• Stack frames are added to the call stack as more recursive calls are evoked until we get to the base case. In this scenario, the base case is when the array is empty, denoted by arr.length === 0.

Before making use of recursion, it is helpful to think carefully of your base case(s) so as to prevent a stack overflow or non-terminating function.

For our problem, it is ideal for us to stop recursing when the numbers array is empty.

We could as well decide not to return the recursive case immediately, rather, we could save the value, log the value to the console and afterwards, return the value. This is where the post-recurse phase comes in.

const numbers = [1, 2, 3, 4, 5];

function sum(arr) {
  // base case
  if (arr.length === 0) {
    return 0;
  }
  // pre recurse
  let head = arr.shift();
  // recursive case
  let result = head + sum(arr) // recursive call;
  // post recurse
  console.log({ element: head, result });

  return result;
}

console.log(sum(numbers));

The post-recurse phase gives us access to the point in the call stack where the base case is reached so that we can operate over the current state of the call stack from top to bottom.

When to use recursion

Recursion is mostly used to solve problems that can be broken down into smaller bits and solved at those smaller levels such that solving the problem at those smaller levels makes solving the whole problem easier. In simple but technical terms, divide and conquer. It is a declarative form of looping over a collection (or recursive data structure) much like the imperative for-loop which you’re likely to be more familiar with. Hence, it is mostly used in languages that promote a declarative style of programming (functional languages).

A recursive data structure is one that references itself by definition just like a recursive function.

Example of a recursive data structure is a graph (including trees and linked lists).

• To define a tree or graph, we could say that it is either a node/vertex with children/adjacents that are also nodes/vertices or leaves.

• To define a linked list, we could say that it is either a node with a next/previous node or a terminus/null value.

The pre-recurse and post-recurse phases in a recursion are mostly used in problems that require you to track your path in a 2D dimensional array or a graph. This concept is called pathing. Pathing simply means that as you recurse over a recursive data structure, you push your current location into an array and pop it when a condition isn’t met while in that location. You do this until you a certain condition is met at a desired location in the data structure such that at the end of the operation, you have a path from the head/start of the graph to the point where the condition was met.

We will go over a more practical but advance problem that showcases the usefulness of recursion in the next part of this series.

In conclusion, recursion is a great tool to have in your toolbox as a programmer and a good understanding of it can enable you solve complex problems in a simple manner by using the divide and conquer approach. I hope this article decomposes the mechanics of recursion for you and give you a good foundation you can build upon. In the later parts of this series, we will explore a more practical use case of recursion and we will also examine how to optimize our recursive functions to make them performant. Thanks for reading and I hope you enjoyed it.