Introduction

Recursion can be tricky. There are four fundamental patterns good to know.

To be honest, I just came up with the names myself lmao, but these patterns are pretty common.

The "Return Value Chain" Pattern

function findInTree(node, target) {
  // Common mistake: forgetting to return the result
  if (node.value === target) {
    return node; // Found it!
  }

  if (node.children) {
    for (const child of node.children) {
      // Common mistake: not capturing the return value
      const found = findInTree(child, target); // Important!
      if (found) return found; // Pass it up!
    }
  }

  return null; // Nothing found in this branch
}

When calling findInTree(child, target) again, you can't return it then. Otherwise what would happen is that the function would stop after the first child since it would return right away even though you didn't find the target.

The "Modify as You Go" Pattern

function multiplyAllValues(node, multiplier) {
  // Modify current node
  node.value *= multiplier;

  // Recurse on children if they exist
  if (node.children) {
    node.children.forEach((child) => {
      multiplyAllValues(child, multiplier);
    });
  }
  // No return needed if just modifying
}

Here we modify the value in place. Because objects are passed by reference, the changes will be reflected in the original object. When we say "reference" we mean that the object is not copied. The same object in the function points to the same memory location as the original object. That's why when you modify what e.g. field of obj points to, it will be reflected in the memory location of obj.

The "Collect Results" Pattern

function getAllLeafNodes(node, results = []) {
  // Base case: it's a leaf
  if (!node.children || node.children.length === 0) {
    results.push(node);
  } else {
    // Recurse on all children
    node.children.forEach((child) => {
      getAllLeafNodes(child, results);
    });
  }
  return results;
}

Here we're modifying the results array as we go. Arrays are objects under the hood, so they are passed by reference. That means that the changes will be reflected in the original array (the same one throughout the recursion).

It's important not to forget to pass the results array when calling the function recursively. And make sure to return the results array at the end. Otherwise nothing will be returned.

The "Keep track of path" Pattern

function findNodeAndPath(
  nodes: Array<Node>,
  targetId: string,
  path: Array<Node> = []
): Array<Node> | null {
  for (const node of nodes) {
    path.push(node);

    if (node.id === targetId) {
      return path;
    }

    if ("children" in node && node.children.length > 0) {
      const found = findNodeAndPath(node.children, targetId, path);
      if (found) return found;
    }

    path.pop();
  }
  return null;
}

Here we're keeping track of the path to the target node as we go. When we return the path, the last element is the target node. The first element would be the upper most parent node.

Fundamental Traversal Patterns

Comments

More from this blog

Become a cracked product engineer today

Bipedal, humanoid, and the words for creature shapes in games

Lerp and smoothstep, what they actually do

IK and FK, what they actually are

How to make your textures fast on the GPU

Introduction

The "Return Value Chain" Pattern

The "Modify as You Go" Pattern

The "Collect Results" Pattern

The "Keep track of path" Pattern

Command Palette

Comments

More from this blog

Introduction

The "Return Value Chain" Pattern

The "Modify as You Go" Pattern

The "Collect Results" Pattern

The "Keep track of path" Pattern