Take recursion in control

/** Aggregate values of nodes in a tree */
const aggregateValues = <T>(rootNode: Node<T>): T[] => {
  const result: T[] = [];
  let nodes = [rootNode];

  while(nodes.length !== 0) {
    result.push(...nodes.map(n => n.value));
    const nextNodes = nodes.flatMap(n => n.nodes);
    nodes = nextNodes;
  }

  return result;
}

For starters, loop implementation is much more complicated, because it has to track intermediate values, that are processed. It’s fairly typical for imperative solutions. Regarding complexity they are exact (each node is accessed only once). The recursive function may reach the maximum call stack size exceeded problem (just like any recursive function in languages, that don’t have tail recursion).

We proved that for recursive types, it’s nice to have a recursive function, because they naturally match each other. We’ll talk more about examples later on.

Since loops and recursion are interchangeable, the best answer to “When to use recursion?” would be:

Use recursion whenever it’s more readable than loop, and use loop whenever it’s more readable than recursion. The definition of “readable” depends on the code being written (sometimes a certain function can be treated as a black box, and then it doesn’t matter), and team familiarity with recursion. Recursion tends to be more declarative and readable when used with recursive types and definitions, but this isn’t a golden rule. People are taught using loops from the beginning of their career, which is why loops are more natural to them, but it’s only a matter of a habit.

At some point in my life, when I got used to recursion, it became more natural to me to solve problems than with old-school loops. For me, recursion is more sexy.

When not to use recursion?

The primary problem with recursion is its inability to track state because usually recursive functions are stateless (due to each execution being scoped). This implies passing an intermediate state as function parameters, which clutters the solution and makes function’s API dirty, which we will see later in examples.

If there is an absolute need for a set of operations to be stateful, then the recursion is probably not a good idea.

During (self) code reviews, I’ve often asked myself how a person without recursion experience will read the function, and if the implementation would be clear for them. More than once the answer was “just rewrite this using loop…”, even if I preferred recursion better. After all, it’s more important to leave code readable to others than to ourselves.

Why to practice recursion?

Recursion is just another tool in a programmer’s tool belt. It is also a great mind exercise, which may improve abstract thinking in more obvious situations, and lead to better skills in solving algorithms or writing clearer code.

How to practice recursion?

Since any loop can be replaced with recursion, the best way to learn it would be to throw away all the loops and solve everything with recursion. It will be problematic at the beginning, but a few nice exercises given at the end of this article should speed up the learning process of how to do this.

You don’t need to publish the recursive implementation to a code review if you have time to rewrite the solution to loop before actually submitting it.

Practice – forEach

Let’s take a look at Array.prototype.forEach function, and reimplement that (the basic usage only, with first argument present). It takes an array, a callback, and calls the callback once for each item in the array, passing this item as the callback’s argument.

The first thing we need to do is to determine whether the function can be recursive. My definition above says:

execute some set of operations some number of times N

forEach executes some set of operations (calls a callback) some number of times N (where N = array.length). It seems, that it can be written using recursion.

First thing we want to do is finding repetitive pattern:

1. Call callback for first item in array
2. Call callback for second item in array
3. Call callback for third item in array
4. …

Hm… not very repetitive. Let’s change the approach:

1. Take array’s first item, and “rest” as a new array
2. Call callback for first item.
3. Take array’s (previous rest) first item, and “rest” as a new array
4. Call callback for first item.
5. Take array’s (previous rest) first item, and “rest” as a new array
6. …

Now that’s better! Taking the “first” item from the list and leaving the rest for later is a very common approach in recursive functions. It’s so common, in fact, that it’s supported as pattern matching destruction in Haskell and many functional languages.

The second thing we need to take care of is the recursion base. In this case, we want to stop executing whenever the array we process is empty (because we cannot take the first item from an empty array).

On to the implementation:

const forEach = <T>(array: T[], cb: (v: T) => void): void => {
  // Recursion base
  if (array.length === 0) {
    return;
  }

  // Taking first item, and "rest" from array
  const [first, ...rest] = array;

  // Executing callback on first item
  cb(first);

  // Processing "rest" in a loop - if rest is empty, then it will hit base in next iteration
  forEach(rest, cb);
}

const map = <T, P>(array: T[], cb: (v: T) => P): P[] => {
  // Recursion base
  if (array.length === 0) {
    return [];
  }

  // Taking first item, and "rest" from array
  const [first, ...rest] = array;

  return [
    // Executing callback on first item
    cb(first),
    // Processing "rest" in a loop - if rest is empty, then it will hit base in next iteration
    ...map(rest, cb), // spread operator flattens result, and joins it with result of cb(first)
  ];
}

-- type definition
map :: (a -> b) -> [a] -> [b]
-- recursion base - pattern matching for empty array
map cb [] = []
-- `:` operator normally joins item and list
-- here it can be used to extract first item from array
map cb (first : rest) = cb first : map cb rest

const map = <T, P>(originalArray: T[], cb: (v: T, i: number) => P): P[] => {
  const process = (array: T[], index: number) => {
    if (array.length === 0) {
      return [];
    }

    const [first, ...rest] = array;

    return [
      cb(first, index),
      ...process(rest, index + 1),
    ];
  }

  return process(originalArray, 0);
}

const mapRight = <T, P>(array: T[], cb: (v: T, i: number) => P): P[] => {
  if (array.length === 0) {
    return [];
  }

  const [rest, [last]] = [array.slice(0, -1), array.slice(-1)];

  return [
    cb(last, rest.length),
    ...mapAndReverse(rest, cb),
  ];
}