First described in the classic geometry book Elements, by the ancient Greek mathematician Euclid (ca. 300 BC, at the book VII, proposition 2), the method of finding de greatest common divisor between the positive numbers $a$ and $b$, being $a > b$ consists on the knowledge that the common divisors of $a$ and $b$ are the same of $a - b$ and $b$. Therefore, we can find this greatest common divisor by replacing the largest number ($a$) by the different between the two numbers ($a - b$), repeatedly, until the two numbers are equal. In TypeScript, we can do that like this:

const gcd = (a: number, b: number): number => {
  // When `a` is equal to `b`, return the result
  if (a === b) {
    return a
  }

  // When `a` is bigger than b, calculate the the GCD again
  // with the new `a` being `a - b`.
  if (a > b) {
    return gcd(a - b, b)
  }

  // If the new `b` is bigger than `a`,
  // subtract a from it.
  return gcd(a, b - a)
}

This method can be very slow if the difference between $a$ and $b$ is too large. Thankfully, there’s another method to find the greatest common divisor between two numbers, that can be described as follows:

1. In order to find the greatest common divisor between $a$ and $b$, being $a > b$, perform the division between the two numbers. This operation will give a quotient and a remainder (that we will call $q$ and $r$, respectively). Thus, $a$ can be described as $a = q \times b + r$;
2. If $r$ is equal to 0, we stop, because we found that the greatest common divisor of $a$ and $b$ is $b$. Otherwise, we go back to step 1, making $b$ the new $a$ and $r$ will be the new $b$.

Now, we can start with the implementation of the algorithm above:

const gcd = (a: number, b: number): number => {
  // First, we take the remainder between the division of a and b:
  const r = a % b
  
  // If the remainder is equal to zero, it means that we already found the
  // greatest common divisor, therefore, we return b:
  if (r === 0) {
    return b
  }
  
  // If the remainder is not equal to 0, we call the function again
  // with the new values for a and b:
  return gcd(b, a % b)
}

The implementation is very straightforward and can be read exactly as is described in steps 1 and 2. We can make the function simpler, by checking, directly, if $b$ is equal to zero and only doing the remainder operation afterwards. Therefore, if the function receive a $b$ that is equal to zero, we will know that $a$ is the greatest common divisor:

const gcd = (a: number, b: number): number => {
  if (b === 0) {
    return a
  }
  
  return gcd(b, a % b)
}

This variant is called Euclidean algorithm (in contrast of the first one, which is the Euclid’s algorithm) and it significantly faster than the first implementation.

Alternative implementations

We can also take a different approach. Instead of calling our gcd function recursively, we can implement our function using a while loop (analogous to our first implementation above):

const gcd = (a: number, b: number): number => {
  // Run this loop while a is different of b
  while (a !== b) {
    if (a > b) {
      // Subtracts b from a while a is bigger than b
      a = a - b
      // Go to the next loop
      continue
    }
    // Subtracts a from b when a <= b
    b = b - a
  }
  // Returns the greatest common divisor between a and b
  return a
}

And this is another way (analogous to our second implementation above):

const gcd = (a: number, b: number): number => {
  // Run this loop while `b` is different from 0
  while (b !== 0) {
    // Save the new value for a in a temporary variable
    const newA = b
    // Set b to the modulo of a and b (the remainder of the division between a and b)
    b = a % b
    // Set a to its new value before the next loop
    a = newA
  }
  
  // Now that b is equal to 0, we know that a is the greatest common divisor
  return a
}

Finding the greatest common between three or more numbers

The greatest of three or more numbers is equal the product of the prime factors common to all the numbers (we will explore more of that in a future article), but, you can also calculate the greatest common divisor between pairs of this list of numbers with the same functions we have showed already. So, let’s refactor our gcd function to receive multiple parameters:

const gcd = (...numbers: number[]): number => {
  const calculateGcd = (a: number, b: number): number => {
    if (b === 0) {
      return a
    }

    return calculateGcd(b, a % b)
  };

  return (
    numbers
      // Just to be sure, sort numbers in descendant order:
      .sort((a, b) => b - a)
      // Call `calculateGcd` for each pair in the numbers array:
      .reduce((a, b) => calculateGcd(a, b))
  )
}

Validating our input

Let’s guarantee that our functions should always receive, at least, two numbers and that all numbers must not be negative:

const gcd = (...numbers: number[]): number => {
  if (numbers.length < 2) {
    throw new Error("You must pass, at least, 2 numbers")
  }

  if (numbers.some((number) => number < 0)) {
    throw new Error("The numbers must be >= 0")
  }

  const calculateGcd = (a: number, b: number): number => {
    if (b === 0) {
      return a
    }

    return calculateGcd(b, a % b);
  };

  return (
    numbers
      // Just to be sure, sort numbers in descendant order:
      .sort((a, b) => b - a)
      // Call `calculateGcd` for each pair in the numbers array:
      .reduce((a, b) => calculateGcd(a, b))
  )
}

Consider the following function that calculates the factorial of a number:

const factorial = (n) => {
  let result = 1;

  while (n > 1) {
    result *= n;
    n--;
  }

  return result;
};

The function above was implemented iteratively, that is, it uses a loop to calculate the factorial of a number. However, it is possible to implement the same function recursively (that is, a function that references itself):

const factorial = (n) => {
  if (n === 0) return 1;

  return n * factorial(n - 1);
};

The result of both functions is the same, however, the iterative function is much more efficient (in JavaScript) than the recursive function. In addition, if we try to calculate the factorial of a very large number, we encounter the error RangeError: Maximum call stack size exceeded. Let’s understand why this happens and how we can improve the recursive function.

Call Stack

A call stack is a data structure that stores information about a program’s functions. When a function is called, it is added to the execution stack, as well as all the functions it calls. When a function returns, it is removed from the execution stack. Each function added to the stack is called a stack frame.

In order to understand what is happening, let’s try to represent, graphically, how the calculation of the factorial of 6 is done with the iterative function:

Now, compare it with the substitution model for calculating the factorial of 6 using the recursive function:

Note that, in the iterative function, the arrow shape is linear and we can see the state of each variable at each step. In addition, at each iteration of our loop, a calculation is performed and the variables stored in memory are updated. In the recursive function, the arrow shape is exponential and we cannot see the state of all variables in the first half of the processing. In addition, each time the function is executed, more memory needs to be used to store the resulting values of each execution.

But what does this mean? In order for JavaScript to calculate the factorial of 6 using the iterative function, the while condition is added to the stack, where its calculation is performed, the result variable is updated, and then the executed code block of the while is removed from the stack. This is done until the while condition is false, that is, until the value of n is less than or equal to 1.

In the recursive function, each call to the factorial function is added to the stack as many times as necessary until the if condition is false, that is, until the value of n is less than or equal to 1. This means that, to calculate the factorial of 6, the factorial function is added to the stack 6 times before being executed. And that’s why, when we try to calculate the factorial of a large number (100,000, for example), we encounter the error RangeError: Maximum call stack size exceeded: there is not enough space in the stack to store all the calls to the factorial function.

Introducing Tail Call Optimization

As defined by Dr. Axel Rauschmayer:

[…] whenever the last thing a function does is call another function, then this last function does not need to return to its caller. As a consequence, no information needs to be stored on the call stack and the function call is more like a goto (a jump). This type of call is called a tail call; not increasing the stack is called tail call optimization (TCO).

Now, we have discovered that our factorial calculation function is not tail recursive. But how can we make it tail recursive? With the help of another function:

const factorial = (n) => {
  return factorialHelper(n, 1);
};

const factorialHelper = (x, accumulator) => {
  if (x <= 1) {
    return accumulator;
  }

  return factorialHelper(x - 1, x * accumulator);
};

Now, our function is tail recursive: the last thing it does is call a function (and not calculate an expression, as in the first implementation). Now, let’s see the substitution model for calculating the factorial of 6 with our new factorial function:

The performance is superior to our first implementation, although it still doesn’t beat the performance of the iterative function. However, we still encounter the error RangeError: Maximum call stack size exceeded. But why does this happen? Because, despite our function being tail recursive, current versions of Node.js and browsers (with the exception of Safari) do not implement Tail Call Optimization (despite its inclusion in the EcmaScript specification since 2015).

But how will we solve this problem? With the help of another function, of course! For that, we will rely on the Trampoline pattern:

const trampoline = (fn) => {
  while (typeof fn === "function") {
    fn = fn();
  }

  return result;
};

Our trampoline function consists of a loop that invokes a function that wraps another function (what we call a thunk) until there are no more functions to execute. Let’s see how the implementation of our factorial function would look like with the Trampoline pattern:

const trampoline = (fn) => {
  while (typeof fn === "function") {
    fn = fn();
  }

  return fn;
};

const factorialHelper = (x, accumulator) => {
  if (x <= 1) {
    return accumulator;
  }

  // Now, a function returns another function
  return () => factorialHelper(x - 1, x * accumulator);
};

const factorial = (n) => {
  return trampoline(factorialHelper(n, 1));
};

And now, we can call our factorial function with a large number, without encountering the error RangeError: Maximum call stack size exceeded. Of course, depending on the factorial we want to calculate, we will encounter an Infinity, as it is a very large number (a number greater than Number.MAX_SAFE_INTEGER: 253 - ¹). In this case, we can use BigInt:

const trampoline = (fn) => {
  while (typeof fn === "function") {
    fn = fn();
  }

  return fn;
};

const factorialHelper = (x, accumulator) => {
  if (x <= 1) {
    return accumulator;
  }

  return () => factorialHelper(x - 1n, x * accumulator);
};

const factorial = (n) => {
  // Converting values to BigInt
  //-------------------------------\/----------\/
  return trampoline(factorialHelper(BigInt(n), 1n));
};

Typing our function

And finally, let’s add the necessary types to our factorial function:

type Thunk = bigint | (() => Thunk);

const trampoline = (fn: Thunk) => {
  while (typeof fn === "function") {
    fn = fn();
  }

  return fn;
};

const factorialHelper = (x: bigint, accumulator: bigint): Thunk => {
  if (x <= 1) {
    return accumulator;
  }

  return () => factorialHelper(x - 1n, x * accumulator);
};

const factorial = (n: number) => {
  return trampoline(factorialHelper(BigInt(n), 1n));
};

References

• What happened to proper tail calls in JavaScript?
• Tail Call Optmization
• Limites da recursão em JavaScript, TCO e o pattern Trampoline
• What is an Activation object in JavaScript?
• Factorial
• Tail Recursion Explained - Computerphile
• Tail Call Optimization: The Musical!!