recursion.md

isEven = (n) => n == 1 ? false : n == 2 ? true : isEven(n-2); Take recursion in control.

What is a recursion? Why and when use a recursion? How to write recursive function easily? Take this in control!

What is a recursion?

Recursion is when type is defined by itself.
OK, let's proceed to another topi-... What, what do I hear? Not extensive enough? Right!

When talking about recursion, people usually mean either recursive type or recursive function (which calls itself in its body). We'll focus mostly on recursive functions here.

Let's start with the loop, which everybody knows: loop means "execute some set of operations some number of times N".

Now take a look at recursion. A function is some set of operations, and if the function calls itself, then the function is recursive. Therefore we execute some set of operations some number of times. This number of "iterations" N is defined by "recursion base", which is a condition branching into case without recursion, which effectively stops function execution.

These definitions of loop and recursion basically overlap. This somehow shows, that each loop can be implemented as recursion, and vice-versa.

When to use a recursion?

When I ask this question on tech interviews, I usually receive the answer: tree traversing (sometimes Fibonacci sequence). While this answer is correct, it doesn't explain why the recursion is more intuitive than using loop for the same purpose.

More generalized answer would introduce definition of sequence (which is recursive in case of Fibonacci sequence) or recursive types (like in case of a tree). Let's take a look at the latter one:

interface Node<T> {
  nodes: Node<T>[];
  value: T;
}

We defined Node type which holds value of type T, and reference to child nodes - which are Nodes by themselves. This is typical tree structure which we can travel from root node to children node using recursive function:

/** Aggregate values of nodes in a tree */
const aggregateValues = <T>(node: Node<T>): T[] => [
  node.value
  ...node.nodes.map(n => aggregateValues(n)), // no recursion base, because `map` has it's natural base (not executed callback for empty array)
];

So it looks like the recursive way is a one-liner. Let's take a look at loop implementation:

/** 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 pretty typical for imperative solutions. Regarding complexity they are exact (each node is accessed only once). The recursive function may hit 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. Definition of "readable" depends on code being written (sometimes certain function can be treated as black box, 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 it's not the golden rule. People are taught using loops since the beginning of their career, that's why loops are more natural to them, but it's only a matter of a habit.

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

When not to use recursion?

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

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

During (self) code reviews I often asked myself, how person without recursion experience will read the function, and if the implementation would be clear for him/her. Not once, not twice, 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 an another tool in programmer's tool belt. It also great mind exercise, which may improve abstract thinking in more obvious situations, and lead to better skills in solving algorithms or writing clearer code.

It may also be fun, and even necessary in languages like Haskell.

How to practice recursion?

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

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

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 callback once for each item in the array, passing this item as callback's argument.

The first 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 it's better! Taking "first" item from list, and leaving the rest for later is very common approach in recursive functions (so common, that it's supported as pattern matching destruction in Haskell and many functional languages).

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

Onto 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);
}

This implementation lacks side effects, doesn't modify any variables, therefore it can be read entirely from top to bottom, without remembering any intermediate state. And functions without intermediate state are sexy.

Practice - map

Use the procedure:

1. Can map be recursive? Yes, for the same reason forEach can.
2. What is a repetitive pattern? The same as in forEach, but value returned from callback needs to be returned as map result.
3. What is a recursion base? Empty input array should stop recursion.
4. What is an expected result of recursion base? If we receive empty array as input, we want to return empty array, because there was nothing to iterate over.

Hint: Writing types first is very helpful in determining point 4., and keeping implementation in-place.

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)
  ];
}

Therefore for identity callback (which returns unchanged input: const id = a => a):

Iteration	Input	First	Rest	Result
1	[1,2,3,4]	1	[2,3,4]	[1, ...map([2,3,4])]
2	[2,3,4]	2	[3,4]	[1, 2, ...map([3,4])]
3	[3,4]	3	[4]	[1, 2, 3, ...map([4])]
4	[4]	4	[]	[1, 2, 3, 4, ...map([])]
5	[]	x	x	x

Which finalizes with [1, 2, 3, 4, ...([])] (recursion base), which is simply [1,2,3,4].

As a bonus, let's take a look at the language which is much better fitted for writing recursive functions. Since in Haskell there are no loops all problems need to be solved using recursion, and language provides utilities to work with: pattern matching and destructing. Map implementation in Haskell would look like this:

-- 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

Practice - map with index

Wait, whoa! But Array.prototype.map passes currently processed index as the callback's second argument! That's right. I avoided this implementation detail, because that's one of pitfalls of recursive functions. Since by default we avoid intermediate state, it becomes bothersome to suddenly start working with state.

For recursive map there is no difference between processing original input array, and some array with few items already processed. Therefore there is no way to determine on which position of original array we are.

This usually is overcome by passing intermediate state as the second argument. Normally this pollutes function API, so it's good habit to create some internal process function like so:

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);
}

I think, that this is the moment, when using recursive implementation should be reconsidered. The function already gets complicated, and for-loop implementation may be better because it has state built-in.

My personal opinion though is that map function should not support index. If callback needs index for whatever, then probably it should not use map at all, but some other dedicated function (like times with number of iterations to perform).

For fun: using clever technique we can "cleanup" this implementation, if we play with execution order (iterate items from last):

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),
    ...mapRight(rest, cb),
  ];
}

Summary before exercises

1. Loop is a tool
2. Recursion is a tool
3. Any loop can be replaced by recursion, any recursion can be replaced by loop
4. Recursion is sometimes more readable than loop, and loop is sometimes more readable than recursion
5. Recursion doesn't play good if there is an intermediate state, that has to be tracked
6. Recursion tends to be better for work with recursive types, and writing types first helps with implementing recursion
7. Recursion requires some practice to be easy to write and read
8. Recursion tends to be more declarative, but it's not a value by itself
9. It's best if recursion is a pure function (doesn't modify variables outside of its scope, and doesn't rely on non-const values outside of its scope), otherwise the code will be dirty
10. Think before writing recursion: find repetitive pattern, find recursion base and its return value, ask yourself how to join this processing result with next recursion result. And you are done.

Exercises

Each exercise will challenge your mind to think in a recursive way. Sometimes finding recursive pattern may be really hard, but don't give up. As I've already said - it can learned by practice.

1. Reimplement Array.prototype.reduce (without index support)
2. Implement times(n: number, cb: (n: number) => void) => void function which executes given callback N times, passing current iteration as argument.
3. Implement isEven(n: number) => boolean which verifies whether the number is even or not. It should support natural numbers without support for zero.
4. Implement fibonacci(n: number) => number[] which returns list of N numbers from Fibonacci sequence (e.g. for N = 4 it would return [1, 1, 2, 3])
5. Implement pascal(n: number) => number[] which returns N'th row from Pascal triangle. Hint: Pascal triangle definition is recursive

Next, compare your solutions with solutions, that are allowed to use loop.