If you write functional code, you will encounter problems where a recursive algorithm is an appropriate solution. However, if you've come from an Object Oriented background or you are new to functional programming, you might struggle when it comes time to write your recursive function. I'm going to give you a simple framework for solving these recursive problems.
Understand Your Types
In a recursive function, you always have some input value, some form of work, and some output value. How you return that output might vary, i.e. if you're appending to or mutating some collection, or returning a primitive value from nested calls. Since the latter is easier to type and reason about, let's start there.
Starting with a simple factorial function, the problem domain is maths, so the input and return types will be numbers.
type CalculateFactorial = (factor: number) => number;
Now that I know my function needs to take a number and return a number, lets implement it:
const calculateFactorial: CalculateFactorial = (factor) => {
if (factor === 0) return 1; // !0 returns 1 because …maths
return factor * calculateFactorial(factor - 1);
}
Yes, this does not have tail call optimisation nor is it in a recursive trampoline, but we're building our mental model of recursion step by step. Hold on, we'll get there.
Let's try a problem wherein we want to traverse some tree structure in our function. In this case, I have a set of nested JSON objects.
type Leaf = {
nodeAddress: string;
data: string;
}
type Branch = {
nodeAddress: string;
children: Array<Leaf | Branch>;
}
Well just looking at my types I can already see a base case and recursive type structures!
Lets have a crack at writing this type of recursive function:
const traverseTree = (nodeAddress: string): Branch | Leaf => {
const node = getNodeByAddress(nodeAddress);
const isLeaf = checkIsLeaf(node);
if (isLeaf) {
return {
nodeAddress,
data: getNodeData(node),
};
}
return {
nodeAddress,
children: getNodeChildrenAddresses(node).map(traverseTree)
};
};
So here we can see the function follows the type — if it's a leaf node, we get the data, and if it's a branch node, we get the addresses of its child nodes and map over them with our traversal function. By taking time to consider our types, we've reduced our cognitive load while writing the function.
Check your base case
In every recursive function we have to have a base case. This is the scenario where recursion stops because the function no longer calls itself.
In the first function it was if (factor === 0) return 1;
In the second function it was
if (isLeaf) {
return {
nodeAddress,
data: getNodeData(node),
};
}
You may have been told in the past that you should start by defining your base case in a recursive function, but as we saw above, it can be useful to start by defining your types first. You can't define a base case if you haven't grokked the data structure you're working with.
We saw in the first function that we were taking in and returning numbers, so the base case must be some sentinel number. In the case of factorial, that sentinel value is 0.
In the second function we saw that we had a recursive data structure, so our base case had to be the leaf nodes. This also informed us that our function returned two different things — a Leaf or a Branch.
Define the business logic
A recursive function always involves some work, some business logic. In the simplest case it is a single expression, such as in the factorial solution, where the work is the multiplication operator. In a more complex case, the work may involve mapping, transforming, calculating, asynchronous calls, and more.
Try to be clear in your mind about which parts of the function contain the business logic, and which parts contain the recursion logic. Whenever possible, separate them in code through spacing and ordering.
Optimise
The above implementations have some limitations. They will create a new stack frame for every call, causing them to crash in some cases, in addition to incurring a higher memory cost. In some cases we can use Tail Call Optimisation. This occurs when the recursive function call is in the return position, e.g.
function factorial(factor: number, product = 1): number {
if (factor === 0) return product;
return factorial(factor - 1, product * factor);
}
In this version of factorial, we pass the result of the work into the next function call, which is in the return position. To make it even clearer:
function factorial(factor: number, product = 1): number {
if (factor === 0) return product; // Recursion logic
const newFactor = factor - 1; // Work AKA business logic
const newProduct = product * factor; // Work
return factorial(newFactor, newProduct); // Recursion logic
}
Above we can clearly see that when we call factorial at the end, the calling stack frame is not needed anymore. We've finished with all the variables inside this stack.
If we tried to arrange the original function this way:
const calculateFactorial: CalculateFactorial = (factor) => {
if (factor === 0) return 1; // Recursive logic
const newFactor = factor - 1; // Work
return factor * calculateFactorial(newFactor); // Work & Recursion logic
}
You can see we have a dangling variable factor in the stack frame awaiting the result of the call to calculateFactorial(newFactor) before we can evaluate the multiplication expression and return. This means we have to hold onto this stack frame until the recursion completes!
However, since Nodejs 8 we cannot use Tail Call Optimisation, so what can we do instead?
Recursive Trampoline
A trampoline is the function we use to essentially manage our own stack frames using closures. Here's a very generic trampoline we could use with any function. We're about to use it to "trampoline" the factorial function:
const createTrampoline =
(fn: any) =>
(…args: any[]) => {
let result = fn(…args);
while (typeof result === 'function') {
result = result();
}
return result;
};
This function will take a function as its first and only parameter. It then returns a new function that will call the function we passed it before, and in this case passing through the parameters we supply it. After calling our supplied function (fn), it then checks if the result of our call was a function, if it is, it continues calling it in a loop until it gets a result that is not a function.
Now we have to change our implementation of factorial, just slightly, for this to work:
function factorial(factor: number, product = 1): number | (() => ReturnType<typeof factorial>) {
if (factor === 0) return product;
return () => factorial(factor - 1, factor * product);
}
All we have changed in the function body is that the continue case now creates an anonymous closure function that, when called, will call factorial again with the new values. It now returns this closure function instead of returning a value.
Two important things to notice, based on what we've learned so far:
- The return type now includes a recursive type! It can return
numberor a function calling and returning itself. - The returning closure uses tail call optimisation!
So you can see we create a new function that includes our new factor and new product in the function closure, but each instance of factorial is removed from memory before the next call is executed in our trampoline. Neat eh?
In practice, this winds up looking like trampoline(factorial)(5) where we immediately invoke the function returned by trampoline.
Example Test Suite
Here's the test suite I used for this article:
import { expect } from 'chai';
describe('recursive factorial', () => {
it('factorial without TCO', () => {
function factorial(n: number): number {
if (n === 0) return 1;
return n * factorial(n - 1);
}
expect(factorial(5)).to.equal(120);
expect(factorial(100)).to.equal(9.33262154439441e157);
expect(() => factorial(200000)).to.throw(RangeError);
});
it('factorial with tail call optimisation', () => {
function factorial(n: number, product = 1): number {
if (n === 0) return product;
return factorial(n - 1, product * n);
}
expect(factorial(5)).to.equal(120);
expect(factorial(100)).to.equal(9.332621544394418e157);
expect(() => factorial(200000)).to.throw(RangeError);
// Node has dropped tail call optimisation since node 8
// This may work in some browsers,
});
it('factorial with a recursive trampoline', () => {
const trampoline =
(fn: any) =>
(n: number): number => {
let result = fn(n);
while (typeof result === 'function') {
result = result();
}
return result;
};
function factorial(
n: number,
product = 1
): number | (() => ReturnType<typeof factorial>) {
if (n < 1) return product;
return () => factorial(n - 1, n * product);
}
expect(trampoline(factorial)(5)).to.equal(120);
expect(trampoline(factorial)(-1)).to.equal(1);
expect(trampoline(factorial)(100)).to.equal(9.332621544394418e157);
expect(trampoline(factorial)(200000)).to.equal(Infinity);
});
});
Why don't you try to write your own implementation of a recursive summation function?
Here's the same three test cases, but of course I've changed out the expects and removed the function implementations.
import { expect } from 'chai';
describe('recursive sum', () => {
it('sum without TCO', () => {
function sum(numbers: number[]): number {
// Write me!
}
expect(sum([5, 3, 11, 13])).to.equal(32);
expect(sum([100, 230])).to.equal(330);
expect(() => sum(Array.from({ length: 200000 }, (_, i) => i))).to.throw(
RangeError
);
});
it('sum with tail call optimisation', () => {
function sum(numbers: number[], summation = 0): number {
// Write me!
}
expect(sum([5, 3, 11, 13])).to.equal(32);
expect(sum([100, 230])).to.equal(330);
expect(() => sum(Array.from({ length: 200000 }, (_, i) => i))).to.throw(
RangeError
);
// Node has dropped tail call optimisation since node 8
// This may not throw in some browsers,
});
it('sum with a recursive trampoline', () => {
const trampoline =
(fn: any) => (/* add params and types */) => {}; // Write out the implementation of trampoline yourself, it will help you grok it
function sum(
numbers: number[],
summation = 0
): number | (() => ReturnType<typeof sum>) {
// Write me!
}
expect(trampoline(sum)([5, 3, 11, 13])).to.equal(32);
expect(trampoline(sum)([100, 230])).to.equal(330);
expect(
trampoline(sum)(Array.from({ length: 200000 }, (_, i) => i))
).to.equal(19999900000);
}).timeout(10000); // This may take a while if you use `shift`
});
See if you can get the tests to pass, and let me know how you went in the comments!