Recursion

What’s Recursion?

A recursive function solves a problem by solving smaller instances of the larger problem. It does this by calling itself with different parameters until a base case is reached, and the function simply returns vis-à-vis a non-recursive expression. Recursion is most commonly used to traverse data structures with indeterminate depth, such as multi-dimensional arrays and trees. However, it can be used to solve most any problem that is more typically solved with iteration and mutation (albeit with reservations).

Recursion can be difficult to grasp because it's difficult to understand something by means of it's definition. This post aims to explain how recursion works under-the-hood , why and when to use it, and how it relates to iteration. |'ll use JavaScript to illustrate my points.

Factorial Example

A function that returns the factorial of its argument is a very simple way of illustrating recursion. A factorial of n is the product of every number preceding and including n and is written n!. Take, for example 4!:

1 * 2 * 3 * 4 = 24

Thus, if I were to ask you to write a function that, given a positive integer n returns n! you'd probably write an iterative solution that accumulates the return value:

function factIt(n) {
  if (n <= 1) return 1;
  let acc = 1;
  for (let i = 1; i <= n; i++) {
    acc *= i;
  }
  return acc;
}
expect(factIt(0).toEqual(1); 
expect(factIt(1).toEqual(1); 
expect(factIt(4).toEqual(24); 

What's wrong with this? Nothing at all. It works, and it's efficient enough. Though a few things are a bit inelegant:

1. We are mutating the variable acc. This can make program logic harder to understand and debug, especially with more complex and longer functions.
2. The algorithm is imperative, not declarative. The code reads like machine instructions (which can be good or bad depending on your perspecitve). For example, what does incrementing i have to do with the problem domain?
3. It's verbose, which can make it harder to read. Some argue the more code you have the more opportunities there are for bugs (some argue the opposite).

Now let's implement a recursive solution. The first question to ask yourself when attempting to write a recursive function is: "what's the smallest case of the problem that I can solve?" That's easy, it's n=0 (forget negative numbers for now). 0!, by convention, is 1. So let's do that:

function factR(n) {
  if (n === 0) return 1; 
}
expect(factR(0)).toBe(1);

What's the next biggest case? It's n=1. 1! is also 1. So we can add that case, and this is our base case. Now we have:

function factR(n) {
  if (n <= 1) return 1;
}
expect(factR(1)).toEqual(1);

The next higher case is, 2!, which we can solve by multiplying 2 by the previous number, 1, or generally: n * (n - 1):

function factR(n) {
  if (n <= 1) return 1;
  return n * (n -1);
}
expect(factR(2)).toEqual(2);
expect(fact(3)).toEqual(6);

This works for 2 because there's only one number lower than 2 and greater than 0. And, we get a freebie: it also works for 3 because while there are two numbers lower than 3 but greater than 0, one of them is 1, which is the multiplicative identity. Let's try factR(4):

expect(factR(4)).toEqual(24);  // fails

We get the wrong answer because we're only multiplying n by the one previous value, not all previous values. So, how can we define a factorial in terms of itself? Well, the factorial of any number is that number times the factorial of the previous number. E.g.

4! = 4 * 3!

How do we get the factorial of n-1? We simply call the same factorial function, passing n-1:

function factR(n) {
  if (n <= 1) return 1;
  return n * factR(n -1);
}
expect(factR(4)).toEqual(24);

The Iterative Stack Frame

Before really understanding how recursion works, we have to understand how function-scoped variables are stored in computer memory. All function-scoped variables are stored in a separate space on the stack, which is a data structure in memory much like a stack of plates: The last one in is the first one out. In the case of our iterative version of factorial, we have one "plate" in the stack because the function is called once. Even if the function is called in succession it's never executed from within itself. Here's our iterative factIt again:

function factIt(n) {
  if (n <= 1) return 1;
  let acc = 1;
  for (let i = 1; i <= n; i++) {
    acc *= i;
  }
  return acc;
}

Here is what the (one plate) stack looks like for the call factIt(4):

Code	Stack
let acc = 1;	factIt n 4 acc 1
for (let i = 1; i <= n; i++) acc *= i;	factIt n 4 i 1 acc 1
for (let i = 1; i <= n; i++) acc *= i;	factIt n 4 i 2 acc 2
for (let i = 1; i <= n; i++) acc *= i;	factIt n 4 i 3 acc 6
for (let i = 1; i <= n; i++) acc *= i;	factIt n 4 i 4 acc 24
return acc;	factIt n 4 i 4 acc 24

The Recursive Stack Frame(s)

Now let's examine the stack for the recursive function call: factR(4):

function factR(n) {
  if (n <= 1) {
    return 1;
  }
  return n * factR(n -1);
}

Code	Stack	Notes
if (n <= 1)	factR n 4	4 is not <= 1, so the function doesn't immediately return.
return n * factR(n -1);	factR n 4	This is the recursive case. Execute the function we're in, spawning off another instance of this function. The "parent" function won't return even after spawning a "child" function, because it will have a child function still in memory.
if (n <= 1)	factR n 3 factR n 4	Because the child function has begun executing while the parent function hasn't yet returned, we now have two stack frames each with its own variable context in memory. The most recent function executed has its frame on top.
return n * factR(n - 1);	factR n 3 factR n 4	This is the recursive case again.
if (n <= 1)	factR n 2 factR n 3 factR n 4	Another stack frame has been added on top.
return n * factR(n - 1);	factR n 2 factR n 3 factR n 4	This is the recursive case yet again, now pass 1
if (n <= 1) { return 1; }	factR n 1 factR n 2 factR n 3 factR n 4

The last stack frame has been added. We've entered the base case because n is less than or equal to 1, so we can return from the highest frame on the stack.return n * factR(n-1);

factR
n	2

factR
n	3

factR
n	4

Now that we've returned from the top-most frame,
We can start to "unravel" the stack.

n is 2 and it's being multiplied by
1 which is the value of factR(n-1) returned from the last frame.

return n * factR(n-1);

factR
n	3

factR
n	4

We've returned from the second function call from the top of the stack, which returned 2.
3 * 2 = 6 so we return 6 from this context to the frame underneath.return n * factR(n-1);

factR
n	4

We've returned from the third function call from the top of the stack, which returned 6.
4 * 6 = 24. At this point we are in the parent function context, which was the one that spawned the rest of the functions. When this returns we get our answer!

Problems with Recursion

A serious downside of recursion is potential memory usage. Each level of recursion corresponds to an additional layer on the stack, each with its own copy of variables. Especially with large inputs, this can cause a stack overflow, which is when the program runs out of memory and crashes.

We can avoid this in certain languages by ensuring the recursion is in tail position. When recursion is in tail position, the function returns only the recursive call. In our factR function the recursion is not in tail position because there's multiplication of the result of the recursive call:

return n * factR(n - 1);

We can change our factR function so that the recursive call is in tail position by writing a local recursive function that accepts an accumulator. Note that in this version the local recursive function go returns just the result of the call to itself--there's no more work outside the recursive call:

function factRTail(n) {
  function go(n, acc) {
    if (n <= 1) {
      return acc;
    }
    // This is in tail position:
    return go(n-1, n*acc);
  }
  return go(n, 1);
  }

We've changed the function so that the recursive function is an inner function that takes the state of n as it's decremented and moved the accumulator from outside the recursive call to an argument to the inner function. This means no work is being done after the recursive call. Let's examine the stack so we fully understand how this plays out:

Tail Call Optimization (TCO)

Putting the recursion in tail position allows some languages to perform tail call optimization, which is when the compiler or interpreter can generate machine code that is similar in memory consumption to an equivalent loop. This effectively allows you to use recursion without worrying about excessive memory usage. This is especially important in functional-first languages like Elixir, Scala, F# etc. because non-recursively looping is either discouraged or unavailable.

Scala, for example, provides the @tailrec annotation on functions. If a function is decorated with @tailrec and the compiler can't perform TCO, it will throw a warning.

F# simply does its best effort to perform TCO, but doesn't tell you if it can't. You'd have to check it yourself by calling the function with large inputs.

Whether JavaScript performs TCO depends on the engine. Safari, for example, does optimize for tail recursion, while the Node.js engine has been on-and-off again. With JavaScript, you really can't count on TCO, so it's best to avoid recursion if there's an equally effective iterative solution.

Hopefully we can now see the relationship here between recursion and iteration. They both accomplish the same thing, but via different methods. To remind ourselves, here is the iterative factorial function:

function factIt(n) {
  if (n <= 1) return 1;
  let acc = 1;
  for (let i = 1; i <= n; i++) {
    acc *= i;
  }
  return acc;
}

And here is the recursive version in tail position:

function factRTail(n) {
  function go(n, acc) {
    if (n <= 1) {
      return acc;
    }
    return go(n-1, n*acc);
  }
  return go(n, 1);
}

The iterative version accumulates the answer by counting up from 1 to n and multiplying the accumulator each time by each number leading up to n.

The recursive approach counts down from n, storing each result in the accumulator which it passes to each function context in the stack. The recursive version counts down because the stack unwinds from the most recent call to the first.

Also note that in the recursive version, the locally scoped, recursive function go acts like a loop. But instead of mutating i and acc, it is passed the state of the "loop" (the current number and the accumulator) as parameters.

Recursion As Iteration (Revisited)

Just to emphasize that you can write most anything recursively that you can iteratively, we can write a simple "loop" that prints out each array element, even though at first glance a one-dimensional array is not a recursive data structure...or is it?

First, though, we need a few helper functions:

const head = arr => arr[0] || null;
const tail = arr => arr.slice(1);

expect(head([1, 2, 3])).toEqual(1);
expect(tail([1, 2, 3])).toEqual([2, 3]);

Here's a recursive function that visits each element of the array. Note that the base case is an empty array, since eventually the tail will produce an array with zero length:

function applyF(arr, f) {
  const go = (h, t) => {
    f(h);
    if (t.length === 0) return;
    go(head(t), tail(t));
  }
  go(head(arr), tail(arr));
  }
  >> applyF([1, 2, 3], e => console.log(e));
1
2
3

So, in fact, even a one-dimensional array is a recursive data structure because each element is the head of a tail. Recursion is the only way to explicitly iterate in more pure functional languages such as Haskell and Elixir.

Indeterminate Depth Problems

At the end of the day most problems are best solved with iteration (at least in imperative and non-pure functional languages). That said, data structures with indeterminate depth, such as multi-dimensional arrays and trees are best recursively traversed. As an example, let's write a recursive find function that returns true if any element matches it's el parameter, no matter how deeply nested. Doing this with loops would be awkward, at best. Recursion is more elegant:

const head = arr => arr[0] || null;
const tail = arr => arr.slice(1);

function recursiveFind(arr, el) {
    if (arr.length === 0) {
        // base case if el is never found.
        return false;
    }
    if (arr.includes(el)) {
        // base case if el is found.
        return true;
    }
    const hd = head(arr);
    if (Array.isArray(hd)) {
        // in the case where the head of the array, which
        // is **usually** a single element, is an array we know
        // it's a nested array, so recurse on the head
        return isMember(hd, el);
    }
    // This is the normative recursive case where
    // the tail is an array of > 0 length.
    return isMember(tail(arr), el);
}

// Find "jill" in the haystack:
expect(isMember([1, 2, [3, ["jack", ["jill"]]]], "jill")).toBe(true);

In the case of recursiveFind there are two base cases: when all elements have been exhausted, and when the element is found in an array.

Conclusion

Recursion is particularly well-cut out for certain kinds of problems, namely when it's clear the solution is composed of smaller solutions to the problem, and when a data structure has an unknown depth.

Besides for practical considerations, recursion is interesting because it can be used instead of iteration, which is necessary in certain languages. Additionally, it forces the programmer to think in terms of base cases, which are often the crux of the solution.

Credits

The following were sources that helped me understand recursion:

• Grokking Algorithms: https://livebook.manning.com/book/grokking-algorithms/chapter-3/9
• The Little Schemer: https://mitpress.mit.edu/books/little-schemer-fourth-edition
• Learning a bit of Haskell: https://www.haskell.org/