JavaScript, inside out · Chapter 23 of 51

Recursion

By the end of this chapter you can walk data nested to any depth with a function that calls itself, and know when a loop is the better tool. Build it in your browser: a real editor and terminal, AI that explains, and tests that tell you when it works.

  • Part: The order flow
  • 6 tasks
  • JavaScript
  • In the all labs plan

The first 2 chapters of JavaScript, inside out are free. This one comes with the all labs plan.

Why you need this

Anjali has redesigned the menu. Chai now has a Special section inside it, Snacks has Biscuits inside it, and she wants room for more levels later. Customer comments have the same shape: a comment, replies to it, replies to the replies. Ravi has the opposite problem: his evening log is a chain of 200,000 orders, each pointing to the next, and his counter crashes on it.

With what you know so far, you would write a loop for the top level, a loop inside it for the level below, and a third loop inside that. The code then handles exactly three levels. The day Anjali adds a fourth, everything in it silently disappears from the app.

What you build: 6 tasks

Each task has tests. You write the code in the lab's editor and press Check.

  1. Task 1

    countItems: every item on the menu, at any depth

    Write countItems(node). A node with a children array is a category; a node without one is an item. Return how many items there are under the node, in every category at any depth.

    An item on its own counts as 1, and a category with no children counts as 0. countItems(menu) gives 6 on the starter's menu.

  2. Task 2

    findItem: an item by name, however deep

    Write findItem(node, name). Return the first item whose name is exactly name, searching the children in order and going all the way down into each child before moving on to the next. Return the item object itself, the same object that is in the menu, not a copy.

    Only items match: a category with that name never does. When no item has that name, return null.

  3. Task 3

    menuPaths: the breadcrumb to every item

    Write menuPaths(node). Return an array with one breadcrumb for every item under the node, in menu order: the names from the node you were given down to the item, joined with a space, a greater-than sign and a space, like Menu > Chai > Special > Kesar chai.

    A category with no children gives an empty array. A second call must give the same answer as the first, so nothing may be left over from an earlier call. You may give menuPaths a second parameter with a default value, or use a helper.

  4. Task 4

    threadLines: replies indented by depth

    Write threadLines(comment). Return one line per comment: the author, a colon and a space, then the text, like Anjali: New menu!. The top comment comes first with no indent, and every reply is indented by two spaces per level below the top. Each comment is followed by all of its own replies, in order, before the next comment at its level.

    A comment with no replies gives a single line.

  5. Task 5 · interview question

    Interview: flatten, nested arrays of any depth

    Write flatten(list) with recursion. Return a new flat array of every value inside list, however deeply its arrays are nested, in the same order. Empty arrays add nothing. Falsy values such as 0, null, false and the empty string stay, and objects are kept as they are (only arrays are opened).

    Do not use flat or flatMap: the check fails if either is called. The list you are given must not change.

  6. Task 6

    chainLength: count a 200,000-order chain without crashing

    chainLength(order) counts the orders in a chain, where each order has a next that points to the next order, or null at the end. chainLength(null) gives 0. It is written with recursion now, which works for short chains but crashes on Ravi's 200,000-order log with RangeError: Maximum call stack size exceeded.

    Rewrite it with a loop so that it counts a chain of 200,000 orders. The answers stay the same: 1 for a single order, 3 for three.

What you will learn

  • Base case and recursive case: a function that answers small problems directly and hands smaller pieces to itself.
  • Walking a tree: the shape of the code follows the shape of the data, at any depth.
  • Passing where you are: an extra parameter that carries the depth or the path down.
  • The call stack and its limit: why a very long chain needs a loop.

More in The order flow

Build "Recursion" yourself

Tapri, a chai brand going online, needs its menu, orders and kitchen in code. A real editor and terminal in your browser, AI that explains, and a Check that says when it works.

The first 2 chapters of JavaScript, inside out are free. This one comes with the all labs plan.