DEV Community

Discussion on: When Recursion Comes to Rescue

pentacular profile image
pentacular • Edited

On reflection, I thought this might benefit from an alternative recursive implementation that uses a different partitioning strategy that avoids overconstraint, and does not rely on function calls to implement the recursive policy.

// Note: Assumes that there is a valid topological ordering.
const orderTasks = (tasks) => {
  const resolvedTasks = new Set();
  const orderedTasks = [];
  const unorderedTasks = [...tasks];

  const processFirstUnorderedTask = (task) => {
    for (const dependency of task.depends) {
      if (!resolvedTasks.has(dependency)) {
        // Schedule the task for backtracking.
    // Reduce the size of the problem.

  while (unorderedTasks.length > 0) {
    // Take the first unordered task.
    const task = unorderedTasks.shift();
    // Reduce the size of the problem, or schedule it for backtracking.

  return orderedTasks;

const unorderedTasks = [
    task: "buy groceries",
    depends: [ "go to the store" ]
    task: "make a sandwich",
    depends: [ "buy groceries" ]
    task: "go to the store",
    depends: []

const orderedTasks = orderTasks(unorderedTasks);

console.log(JSON.stringify(orderedTasks, null, 2));
liaowow profile image
Annie Liao Author

Thanks so much for taking a stab at it. As someone who's still learning data structures and CS fundamentals, I really admire your backtracking technique here. It has truly expanded my knowledge of recursion.