When Recursion Comes to Rescue

When practicing solving algorithm problems, we often see questions that make us wonder if we would ever encounter similar situations in the real world (e.g. spiral traversal of a matrix).

This time, however, I came across an interesting algorithm challenge that makes practical sense to me.

Here's the task:

You are given a list of tasks, some of which depend on others.
Write a function tasksInOrder that takes a subset of those tasks and returns an ordered list of all the tasks to run.

To illustrate:

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

// tasksInOrder(tasks, ["make a sandwich"])
// -> [ 'go to the store', 'buy groceries', 'make a sandwich' ]

// tasksInOrder(tasks, ["buy groceries", "make a sandwich"])
// -> [ 'go to the store', 'buy groceries', 'make a sandwich' ]

We all make to-do lists in our daily lives, so I was glad to finally see a function that we can actually put to good, practical use.

Brute Force Approach

As I read the challenge, the first thing that came to mind was a linked-list data structure, as each task has a dependency, or node, that points to another task.

With that, I was able to quickly write out a straightforward (but flawed) solution that traverses both the task list and the given subset.

function tasksInOrder(tasks, subset) {
  let result = []
  for (let task of tasks) {
    if (task.depends.length !== 0) {
      result.unshift(task.depends[0])
    }
  }
  for (let sub of subset) {
    result.push(sub)
  }

  return [...new Set(result)]
}

The solution above does output the desired results in the two sample cases:

// tasksInOrder(tasks, ["make a sandwich"])
// -> [ 'go to the store', 'buy groceries', 'make a sandwich' ]

// tasksInOrder(tasks, ["buy groceries", "make a sandwich"])
// -> [ 'go to the store', 'buy groceries', 'make a sandwich' ]

However, this solution would fail if out task list is not in order:

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

// tasksInOrder(tasksNotInOrder, ["buy groceries"])
// expected -> [ 'go to the store', 'buy groceries' ]
// got -> [ 'buy groceries', 'go to the store' ]

So, how might we follow the dependencies of the given subset that keep recurring in the tasks list in the right order?

Recursive Approach

In order to grab all the dependencies of all the subtasks in the subset, we can:

1. Grab all the dependencies of one subtask
2. Add the dependencies to an array by prepending them, so we can put them in order
3. Repeat step#2 until the subtask has no dependency

Since the recursive solution occurs in the subtasks, we can separate concerns by creating a helper function that focuses on recursion:

function tasksInOrder(tasks, subset) {
  let tasksList = []
  for (let subTask of subset) {
    let foundTask = tasks.find(taskObj => taskObj.task === subTask)
    // invoke helper function
    getDependedTasks(foundTask, tasksList, tasks)
  }
}

// helper function
function getDependedTasks(currentTask, tasksList, tasks) {
  // prepend the current task
  tasksList.unshift(currentTask)
  // base case: when we hit the task with no dependency
  if (currentTask.depends.lenth === 0) {
    return
  }
  // recursive case: 
    // (1) find the task which the current task depends on
    // (2) run the function recursively with the found task
  let nextTask = tasks.find(taskObj => taskObj.task === currentTask.depends[0])
  return getDependedTasks(nextTask, tasksList, tasks)
}

And voilà! With this approach, we see an output of an orderly tasks list, no matter how disorganized the original list is.

Do you see any potential flaws in the recursive approach? Can you think of any other way to tackle this challenge? As always, please let me know in the comments!

Comments

[pentacular]

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.
        unorderedTasks.push(task);
        return;
      }
    }
    // Reduce the size of the problem.
    resolvedTasks.add(task.task);
    orderedTasks.push(task);
  }

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

  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));

[Annie Liao]

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.

[Functional Javascript]

Nice work Annie!

If you've read my posts and comments you'll know I'm anti-recursion. :)
Recursion is always slower, and it always blows up once the data starts getting large.
I do enjoy blowing up recursive functions though LOL

Yours explodes on my machine (will vary by many factors) before 8000 task items.

My iterative will go on for as large of a dataset as you want.

My iterative also clocked 25% faster. So for every 10 hours of CPU your recursive uses, mine will use 7.5 hours. That's 2.5 hours of saved CPU time we can buy beer with. :)

Here's the code....

/**
@func
given a list of tasks, some of which depend on others
- get the set of tasks to complete the job
- returns an ordered list of all the tasks to do

@firstbasecase
the last task to start traversing backwards from, to the root node

@lastbasecase
the task with an empty depends key (root node)

@typedef {{task: string, depends: string[]}} taskObj
@param {taskObj[]} a tasks
@param {string[]} subset
@return {string[]} tasks in order to do
*/
const getTasks = (a, subset) => {
  const f = []; //final output
  const leafTask = a.find(o2 => o2.task === subset[subset.length - 1]); //first basecase
  f.push(leafTask.task);
  let p = leafTask.depends[0]; //preceding id. previous dependency
  while (true) {
    const o = a.find(o2 => o2.task === p);
    p = o.depends[0];
    f.push(o.task);
    if (o.depends.length === 0) { //last basecase
      return f.reverse();
    }
  }
};

//@perftest
const objs = genObjs(1e4);
shuffleElemsDurstenfeldMut(objs);
timeInLoop("getTasks", 1, () => getTasks(objs, ["9999"]));

P.S.
Keep the great posts coming!

P.S.S.
If you want the perftest code, let me know.
I also did some adjustment to your recursive func.

[Annie Liao]

Yeah, I did worry that my recursive approach would blow up when it comes to huge datasets lol. Again, thanks so much for testing it out and for sharing such a well-organized, readable code snippet :)

[pentacular]

l think you are confusing a couple of fundamental things.

• Iteration is generally recursive.

• Recursion does not require function calls.

• Implementing backtracking via a task list doesn't make something less recursive.

I think you may be conflating recursion with function calls.

Also I suggest considering the cost of all of those linear searches you're doing, as the number of tasks increases.

[pentacular]

This is a topological sort.

Recursion is where we take a problem of a given form and either solve it or turn it into a smaller problem of the same form.

This is a valid strategy for this problem, as you've noticed, but it may lead to overconstrained solutions - you're imposing an ordering between subtasks that does not need to be there.