josh oertel

tail recursion in typescript

I recently re-watched a computerphile video about a simple way to avoid stack overflows when using recursive functions. The technique is known as tail recursion.

Note that there are more idiomatic ways to solve the following problems in JavaScript and TypeScript using Array.* methods. You can pretty much do anything with Array.reduce. Also, at the time of this writing, I don’t think Node.js nor Deno support tail recursive calls at all so there’s that.

summing a list of numbers

To sum a list of numbers, you’d loop over the list and add each number to the running total.

sum non-tail-recursive

A non-tail-recursive function that sums a list of numbers could look like the following:

sum_non_tail_recursive.ts
export const sum_non_tail_recursive = (ns: number[], index = 0): number => {
  const n = ns[index];


  if (n === undefined) return 0;


  index += 1;


  return n + sum_non_tail_recursive(ns, index);
};

You can see by looking at the call stack when calling the function, this version of sum is not tail recursive.

count_non_tail_recursive(["a", "b", "", "a"], "a");
1 + count_non_tail_recursive(["a", "b", "", "a"], "a", 1);
1 + 0 + count_non_tail_recursive(["a", "b", "", "a"], "a", 2);
1 + 0 + 0 + count_non_tail_recursive(["a", "b", "", "a"], "a", 3);
1 + 0 + 0 + 1 + count_non_tail_recursive(["a", "b", "", "a"], "a", 4);
1 + 0 + 0 + 1 + 0;
1 + 0 + 1 + 0;
1 + 1 + 0;
2 + 0;
2;

A triangular shape forms because the “work” isn’t completed until the recursion has ended. Sometimes the triangle becomes so big that it can’t all fit on the stack. This is what’s known as a stack overflow.

sum tail-recursive

A tail-recursive implementation of sum might look like this:

sum_tail_recursive.ts
export const sum_tail_recursive = (
  ns: number[],
  index = 0,
  total = 0,
): number => {
  const n = ns[index];


  if (n === undefined) return total;


  index += 1;
  total += n;


  return sum_tail_recursive(ns, index, total);
};

When looking at the call stack, notice how the running total is carried along to the next call of sum. This is pretty characteristic of tail recursive functions.

count_tail_recursive(["a", "b", "c", "a"], "a");
count_tail_recursive(["a", "b", "c", "a"], "a", 1, 1);
count_tail_recursive(["a", "b", "c", "a"], "a", 2, 1);
count_tail_recursive(["a", "b", "c", "a"], "a", 3, 1);
count_tail_recursive(["a", "b", "c", "a"], "a", 4, 2);
2;

count occurrences in a list

To count the number of times an element appears in a list, loop over the list and check if the current element is equal to the target element. If they are equal, add 1 to the tally otherwise add 0.

count non-tail-recursive

count_non_tail_recursive.ts
export const count_non_tail_recursive = <E>(
  elements: E[],
  element: E,
  index = 0,
): number => {
  const candidate = elements[index];


  if (candidate === undefined) return 0;


  const equal = candidate === element;


  index += 1;


  return +equal + count_non_tail_recursive(elements, element, index);
};

Again, the “work” is delayed until the recursion is done.

sum_non_tail_recursive([3, 4, 5]);
3 + sum_non_tail_recursive([3, 4, 5], 1);
3 + 4 + sum_non_tail_recursive([3, 4, 5], 2);
3 + 4 + 5 + sum_non_tail_recursive([3, 4, 5], 3);
3 + 4 + 5 + 0;
7 + 5 + 0;
12 + 0;
12;

count tail-recursive

In the tail-recursive version, the count is passed along to each recursive call.

count_tail_recursive.ts
export const count_tail_recursive = <E>(
  elements: E[],
  element: E,
  index = 0,
  count = 0,
): number => {
  const candidate = elements[index];


  if (candidate === undefined) return count;


  index += 1;


  const equal = candidate === element;
  count += +equal;


  return count_tail_recursive(elements, element, index, count);
};

Just like the tail-recursive version of the sum function above, the calculation is performed before the recursion and the accumulated result gets passed along.

sum_tail_recursive([3, 4, 5]);
sum_tail_recursive([3, 4, 5], 1, 3);
sum_tail_recursive([3, 4, 5], 2, 7);
sum_tail_recursive([3, 4, 5], 3, 12);
12;

summary

While writing this post I realized that this style of recursion is a lot like performing a while loop. In a while loop all the work is done in the body of the loop and when you’re done, you jump back to the top of the loop to do it all again.

resources