Tail calls

A tail call is the last thing a function does

In the Stack overflow lesson, you saw that recursion can run out of room. (Recursion means a function that calls itself.) Every call that has not finished yet takes up space on the call stack. The space for one call is called a frame. A frame holds the call's parameters and the place to go back to when the call ends.

This lesson asks one question. When a function calls another function as its very last step, does the first function still need its frame?

An engine is the part of a browser or Node that runs your JavaScript. Some engines can make use of tail calls. A proper tail call, or PTC, means the engine drops or reuses the calling function's frame before the tail call starts. Then the stack does not grow.

ES2015, the 2015 edition of JavaScript, asks every engine to do this in strict mode. (Strict mode is the stricter set of rules you turn on by writing "use strict" at the top of a file or function.) In practice, only Safari's engine, JavaScriptCore, does it today.

This lesson stays on tail calls. Other lessons cover the topics next to it:

• Advanced recursion shows how to solve problems with recursion.
• The Stack overflow lesson covers stack limits and how to swap recursion for a loop.
• The Stack frames lesson covers what is inside a frame.

Here you will learn three things: which calls are in tail position, what proper tail calls are, and what to use instead today.

Start with a small program. It has three functions, and each one calls finish(). finish() prints a line and returns the label it was given.

1"use strict";2 3function finish(label) {4  console.log("finish " + label);5  return label;6}7 8function direct() {9  return finish("direct");10}11 12function addAfter() {13  return "value " + finish("add");14}15 16function rightSideTail(ready) {17  return ready || finish("right");18}19 20console.log(direct());21console.log(addAfter());22console.log(rightSideTail(false));

• Line 9 is a tail call. direct() returns exactly what finish() returns.
• Line 13 is not a tail call. After finish() returns, addAfter() still has to put "value " in front of the result.
• Line 17 may surprise you. || means "or". If ready is false, JavaScript runs the right side and returns its result. That result is the whole return value, so the call on the right is in tail position.

The program prints six lines, in this order: finish direct, direct, finish add, value add, finish right, right. The output can't tell you whether the engine reused a frame. It only shows the order the calls ran in.

Each row of the next table is one way to write a return. Read across: the code, whether the call is in tail position, and why.

The JavaScript specification (the spec) is the official rulebook for the language. Its tail-call rule has two checks:

1. The code must be in strict mode.
2. The call must be the last thing in a return.

|| ("or"), && ("and"), and ?? ("use the right side if the left is null or undefined") may skip their right side. For these three, the spec looks only at the right side. A call on the left is never in tail position, because JavaScript must still check its result.

ES2015 added a rule called proper tail calls. It says: for a tail call in strict-mode code, the engine must drop or reuse the current function's frame before it starts the next call. In the spec, the step that does this is called PrepareForTailCall.

Two details matter:

• The rule only applies in strict mode. Older, non-strict code has features that look back at the calling function, and those need its frame to stay.
• The rule changes how much stack space a program uses. It does not change the answer. An engine with PTC and an engine without it compute the same sum. The only difference is whether deep tail recursion keeps adding frames.

The next program runs only in Node. V8 is the engine inside Chrome and Node. The program calls two strict tail-recursive functions 100000 levels deep: countDown on line 5 and sumTo on line 10. Lines 41 and 42 do the same work with a trampoline, which you will meet later in this lesson. A RangeError here means the stack ran out of room.

1"use strict";2 3function countDown(n) {4  if (n === 0) return "done";5  return countDown(n - 1);6}7 8function sumTo(n, acc = 0) {9  if (n === 0) return acc;10  return sumTo(n - 1, acc + n);11}12 13function trampoline(thunk) {14  let current = thunk;15  while (typeof current === "function") current = current();16  return current;17}18 19function countDownThunk(n) {20  if (n === 0) return "done";21  return () => countDownThunk(n - 1);22}23 24function sumThunk(n, acc = 0) {25  if (n === 0) return acc;26  return () => sumThunk(n - 1, acc + n);27}28 29console.log("node", process.version);30console.log("v8", process.versions.v8);31try {32  console.log("plain-countdown", countDown(100000));33} catch (error) {34  console.log("plain-countdown", error.name);35}36try {37  console.log("tail-sum", sumTo(100000));38} catch (error) {39  console.log("tail-sum", error.name);40}41console.log("trampoline-countdown", trampoline(() => countDownThunk(100000)));42console.log("trampoline-sum", trampoline(() => sumThunk(100000)));

node v22.x
v8 12.4.x
plain-countdown RangeError
tail-sum RangeError
trampoline-countdown done
trampoline-sum 5000050000

So don't write JavaScript that needs PTC to work, unless you know exactly which engines will run it and you have tested them. If your code must handle any depth, use one of the safe patterns later in this lesson.

WebKit is the project behind Safari. Its engine, JavaScriptCore, does proper tail calls. WebKit says the gain is memory: frames that a tail call removes don't stay on the stack.

WebKit also names the cost: those frames are missing when you debug. To help, it has a tool called ShadowChicken. While the debugger is open, ShadowChicken keeps a separate record of recent calls, so it can show the missing frames.

The V8 team built proper tail calls and tested them. Then they decided not to turn them on. They gave two reasons:

• Missing frames make debugging and error.stack less useful. (error.stack is the text that lists the calls that led to an error.)
• Keeping a separate record of calls all the time, just in case, costs too much speed and memory.

People from Mozilla (who make Firefox) and Microsoft on the JavaScript standards committee agreed. They suggested a different idea: a special word you write in the code to ask for a tail call. You will see it later in this lesson.

Each row of the next table is one engine family. Read across: the engine, whether it does proper tail calls, and what that means for you.

Here is sumTail. It adds the numbers from n down to 1. It uses an accumulator: an extra parameter, acc, that carries the running total from call to call.

On line 5, the addition acc + n happens first, inside the arguments. Then line 5 returns the call directly, with nothing left to add. So it is a tail call. An engine with PTC can reuse the current frame for the next call. V8 in Node does not, so its stack grows by one frame for each call.

1"use strict";2 3function sumTail(n, acc = 0) {4  if (n === 0) return acc;5  return sumTail(n - 1, acc + n);6}7 8console.log(sumTail(4));Run

This is a model to help you learn. It does not look inside your browser. The code really computes 10. The two frame counters show what an engine with PTC may do, next to what V8 does today.

You can avoid deep stacks today, in every engine, with two small ideas:

• A thunk is a function with no parameters that holds work for later, such as () => sumThunk(3, 4). Nothing runs until something calls it.
• A trampoline is a loop that keeps calling thunks. It stops when it gets back something that is not a function. That value is the answer.

The recursive function doesn't call itself. Instead, it returns a thunk for the next step. Then the loop calls that thunk. Each step ends and goes back to the loop, so the call stack never grows.

1function trampoline(thunk) {2  let current = thunk;3  let hops = 0;4  while (typeof current === "function") {5    current = current();6    hops += 1;7  }8  return { value: current, hops };9}10 11function sumThunk(n, acc = 0) {12  if (n === 0) return acc;13  return () => sumThunk(n - 1, acc + n);14}15 16const result = trampoline(() => sumThunk(4));Run17console.log(result.value);18console.log(result.hops);

The code prints 10 and then 5. The 5 is the number of hops, meaning turns of the loop. There are five hops, not four, because the first thunk, () => sumThunk(4), counts too. With n = 100000, the same code still works in Node, where plain tail recursion throws.

Now run both versions in the browser you are using. The plain version is strict and tail-recursive. The trampoline version uses thunks. The result is labelled your browser, because Safari can give a different result from Chrome and Firefox.

1"use strict";2 3function countDown(n) {4  if (n === 0) return "done";5  return countDown(n - 1);6}7 8function trampoline(thunk) {9  let current = thunk;10  while (typeof current === "function") current = current();11  return current;12}13 14function countDownThunk(n) {15  if (n === 0) return "done";16  return () => countDownThunk(n - 1);17}

Start with small numbers, then try bigger ones. If the plain version throws RangeError, the trampoline should still return done. If the plain version also returns done, there are two possible reasons:

• The number is small enough to fit on the stack.
• Your browser does proper tail calls for this code, as Safari does.

A proposal is a suggested new feature for JavaScript. TC39, the committee that decides on JavaScript features, reviews each one. The syntactic tail calls proposal wanted you to mark a tail call in your code. The usual spelling was return continue f(x).

The mark would do two jobs:

• It would say: "I am fine with this function's frame being dropped."
• The engine could stop with an error if the marked call was not really a tail call.

1function factorial(n, acc = 1) {2  if (n <= 1) return acc;3  return continue factorial(n - 1, acc * n);4}

The name is still worth knowing. When people say "syntactic tail calls", they mean a mark you write in the code. That is different from the ES2015 rule, which applies to tail calls with no mark at all.

Most code should stay easy to read. Choose by how deep your data can get:

• If the data is shallow and you trust it, plain recursion is fine.
• If users or other programs decide the depth, or there is no limit, don't depend on PTC. Use a loop, your own stack, or a trampoline.

1function visitMenu(node, path = []) {2  const nextPath = path.concat(node.label);3  if (node.children.length === 0) return [nextPath.join(" > ")];4  return node.children.flatMap((child) => visitMenu(child, nextPath));5}6 7const menu = {8  label: "Home",9  children: [10    { label: "Courses", children: [{ label: "JavaScript", children: [] }] },11    { label: "Pricing", children: [] },12  ],13};14 15console.log(visitMenu(menu).join(" | "));

Line 4 calls visitMenu again for each child, inside flatMap. (flatMap runs a function on each item and joins the arrays it gets back into one array.) This is clear for small menus. But it is not a safe plan for a huge menu that users built.

For deep data, use your own stack: an array of nodes still to visit, handled by a while loop. Or use a trampoline, if keeping the recursive shape matters to you.

Each row of the next table is one way to handle deep work. Read across: the approach, how it keeps the stack small, and when to use it.

• If speed is your reason for changing code, measure first.
• If you don't trust the depth, use a loop or your own stack.
• Use a trampoline when the recursive shape matters and the extra functions it creates are fine.
• Don't depend on PTC unless you have tested every engine that will run your code.

Common misconceptions

These four names sound alike. Each row says what one name means, and what it does not mean.

Practice exercises

"use strict";
function finish(label) {
  console.log("finish " + label);
  return label;
}
function notTail() {
  return "value " + finish("add");
}
console.log(notTail());

function trampoline(thunk) {
  let current = thunk;
  let hops = 0;
  while (typeof current === "function") {
    current = current();
    hops += 1;
  }
  return { value: current, hops };
}
function sumThunk(n, acc = 0) {
  if (n === 0) return acc;
  return () => sumThunk(n - 1, acc + n);
}
console.log(trampoline(() => sumThunk(4)).hops);

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

function collectLabels(root) {
  const stack = [{ node: root, path: [] }];
  const labels = [];
  while (stack.length > 0) {
    const { node, path } = stack.pop();
    const nextPath = path.concat(node.label);
    if (node.children.length === 0) labels.push(nextPath.join(" > "));
    for (const child of node.children) stack.push({ node: child, path: nextPath });
  }
  return labels;
}

First use the rules for tail position. Then use the facts about which engines do proper tail calls.

Key takeaways

• A tail call returns another call's result straight away. If work is left after the call, it is not a tail call.
• ES2015 asks for proper tail calls in strict mode, but most engines don't do them.
• Safari's engine, JavaScriptCore, is the main browser engine that does them. Treat V8 (Chrome and Node) and SpiderMonkey (Firefox) as engines without them.
• Trampolines, loops, and your own stack are the safe answers for deep recursion today.