Recursion

What is recursion?

In mathematics and computer science, recursion is the process of defining the solution to a problem in terms of smaller versions of the problem itself. In computer science this solution involves a function that calls itself directly or indirectly. In mathematics this may define an infinite number of instances, but in computer science the recursive algorithm always contains a "terminating case" that prevents the occurrence of an infinite chain of instances.

Let's consider a mathematical function f(n) = 2 ⁿ, in which n is any non-negative integer, and rewrite it as a recursive function:

f(n) = 2 n

f(0) = 1
f(n) = 2 × f(n − 1)

f(3) = 2 × f(2)                   ⇒ 
f(3) = 2 × 2 × f(1)            ⇒ 
f(3) = 2 × 2 × 2 × f(0)     ⇒
f(3) = 2 × 2 × 2 × 1 = 8 

function f(n) {
  if (n === 0) { return 1; }
  else {
    return 2 * f(n - 1);
  }
};

console.log( f(3) ); // logs: 8

When the function in the example above calls itself (f(n − 1)), the currently running function is paused. This continues until the outputs of all called functions have been returned. The first paused function ended last by returning the final result.

A recursive algorithm must have one or more base cases (also called base steps or simply bases). In a base case the function produces the most trivial, the "simplest" possible, result, without recurring. In the above example, the base case is f(0) = 1. The base must always eventually be reached, which breaks the chain of recursion. Therefore the base case is sometimes also called the "terminating case".

A recursive algorithm must also have one or more recursive cases. In a recursive case the function recurs, i.e., calls itself: a recursive case contains a recursive call. The recursive cases can be seen as break downs of the problem into smaller or simpler versions of the problem itself. The recursive call uses the same algorithm to solve such smaller/simpler version of the problem. In the example above f(n) = 2 × f(n − 1) is the recursive case. It multiplies two by a recursive call, to solve a smaller/simpler version (f(n − 1)) of the problem. Recurring the recursive cases must work towards and eventually reach the base case, which ends the recursion.

Recursion versus iteration

In the example above, the "explicit function", f(n) = 2 ⁿ, can be seen as an iterative definition: f(3) = 2 × 2 × 2. In a loop we multiply 2 by 2, or, if we write f(3) = 1 × 2 × 2 × 2: in a loop we multiply 1 by 2, n = 3 times. If we translate this to JavaScript code:

function f(n) {
  let result = 1; // base case
  for (let i = 0; i < n; i++) {
    result *= 2;
  }
  return result;  
};

console.log( f(3) ); // logs: 8

This looks somewhat similar to recursion. Yet, recursion uses a function that calls itself where iteration uses a loop. And there are more differences that will be covered in the rest of this chapter.

A recursive algorithm is often shorter, simpler and may be more elegant than an iterative algorithm. However, a recursive algorithm is generally not the most efficient solution in terms of memory usage (see next section).

Any problem that has a recursive solution also has an iterative solution and vice versa. To make a program most efficient, a programmer may decide to use iteration instead of recursion. However, rewriting a recursive algorithm as an iterative algorithm is not always trivial. It may definitely be worth the effort to rewrite simple recursive algorithms (tail recursion, see below) as a loop, but rewriting a more complex recursive algorithm often results in a long and complicated iterative algorithm that is difficult to understand and maintain.

Call stack

Information about the active, running functions of a computer program is stored in a stack in memory, which is called the call stack.

After each call of a function, its execution information (execution context) is pushed onto the top of the call stack as a new entry. The call stack consumes memory, so it is important to keep the number of active entries as low as possible. Moreover, there is a maximum memory occupation allocated for the call stack. Writing more data to the call stack than what is allocated for that stack results is a stack overflow.

When a function calls another function or calls itself (recursion), the currently running outer function is paused and a new entry is saved onto the outer function's entry in the call stack. After execution of the inner function, the top entry of the call stack is removed and execution of the paused outer function resumes.

The call stack of the example above can be visualized as:

f(0) = 1 
f(1) = 2 × f(0)
f(2) = 2 × f(1)
f(3) = 2 × f(2)

After the algorithm filled the call stack with all the algorithm's calls, removing entries from the top down starts. Once f(0) finished execution, the top entry gets removed and f(1) resumes execution with f(0) = 1. This process continues until f(3) finishes execution with 2 × 2 × 2 × 1 = 8.

The maximal number of entries in the call stack was 4 as we can see. We say that the recursion depth of this algorithm is n + 1.

The iterative algorithm for this problem only requires one entry in the call stack, regardless what n is. This is more memory-friendly and there is no danger of a stack overflow.

Tail recursion

Tail recursion is recursion where recursive calls do not need to be saved on the call stack. The last statement is (or returns) just a recursive call. Tail recursive algorithms are essentially iterative.

The next example calculates the greatest common divisor (gcd) of two integers being an implementation of the Euclidean algorithm.

"use strict";
function gcd(a, b) {
  if (b === 0) { return a; }
  else { return gcd(b, a % b); }
};

console.log(gcd(12,8)); // logs: 4

gcd(12,8) ->
gcd(8,4)  ->
gcd(4,0)  ->  4

function gcd(a, b) {
  while (b > 0) {
    [a, b] = [b, a % b]; // array destructuring, see remark below
  }
  return a;
};

console.log(gcd(48,18)); // logs: 6

The final action in the recursive algorithm above is just calling itself. Each time this happens, the calling function basically completely finished. So essentially the calling function could be removed from the call stack. Modern JavaScript engines actually do this as part of "tail call optimization", provided that the code is in strict mode. Nevertheless, rewriting tail recursive algorithms as iterative algorithms is generally relatively simple and the resulting iterative algorithm is generally also short and equally easy to understand and maintain.

In the case of recursion where recursive calls do need to be saved on the call stack, like the 2 to the power n example from the beginning of this chapter, the calling function is not "in it’s final state" when the recursive call is made. The calling function pauses because it needs the result of the called function to finish. Rewriting non-tail recursive algorithms as iterative algorithms is generally more complicated. Generally we need to add an extra variable, which gets assigned the "base case" and keeps track of the computation in the following loop. The loop itself can be seen as a translation of the recursive case. See the example from the beginning of this chapter. By the way, it is also possible to write this function as a tail recursion, but the iterative alternative is much more elegant.

function f(n, current_val = 1) {
  if (n === 0) { return current_val; }
  else {
    return f(n - 1, current_val * 2);
  }
};

console.log( f(3) ); // logs: 8
console.log( f(1) ); // logs: 2
console.log( f(0) ); // logs: 1

Examples

Factorial

/**
* @param n is an integer such that n >= 0
*/
function fact(n) {
   if (n == 0) { return 1; }
   else { return n * fact(n - 1); }
};

console.log(fact(4)); // logs: 24

/**
* @param n is an integer such that n >= 0
*/
function fact(n) {
  let result = 1; // base case
  for (; n > 0; n--) { result *= n; }
  return result;
};

console.log(fact(5)); // logs: 120

Traversing nested objects

Suppose we have objects that contain nested objects, i.e., property values are objects again. Then we want a function that copies all non-object-valued properties of an object, including of all of its nested objects, into one new object. Doing this without recursion will result in long and complicated code. Next example uses recursion:

const someObject = {
  a: 1,
  b: 2,
  subObj1: {
    c: 3,
	d: 4,
	subObj2: {
	  e: 5,
	  subObj3: {
	    f: 6,
		g: 7
	  }
	}
  }
}

const leveledObject = {};

function levelSomeOject(obj, leveledObj) {    
    for (const propName in obj) {	  
      if (typeof obj[propName] === 'object' &&  obj[propName] !== null ) { 
	    levelSomeOject(obj[propName], leveledObj);
      }
	  else { leveledObject[propName] = obj[propName]; }
    }
};

levelSomeOject(someObject, leveledObject);

console.log(leveledObject); // logs: { a: 1, b: 2, c: 3, d: 4, e: 5, f: 6, g: 7 }

Fractal

const canvas = document.getElementById("canvasFractal");
const ctx = canvas.getContext("2d");

canvas.width = 400;
canvas.height = canvas.width * 0.68;
ctx.strokeStyle = '#558000';
ctx.lineWidth = 0.5;

drawTree(canvas.width/2, canvas.height, 90, 25, 14, canvas.height/105);
 
function drawTree(x1, y1, angle, branchAngle, depth, scale){
  if (depth > 0){
    const x2 = x1 + (Math.cos(-angle * Math.PI / 180) * depth * scale);
    const y2 = y1 + (Math.sin(-angle * Math.PI / 180) * depth * scale);
    drawLine(x1, y1, x2, y2);
    drawTree(x2, y2, angle - branchAngle, branchAngle, depth - 1, scale);
    drawTree(x2, y2, angle + branchAngle, branchAngle, depth - 1, scale);
  }
};

function drawLine(x1, y1, x2, y2){
  ctx.beginPath();
  ctx.moveTo(x1, y1);
  ctx.lineTo(x2, y2);
  ctx.closePath();
  ctx.stroke();
};