DEV Community

Discussion on: When Recursion Comes to Rescue

functional_js profile image
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....

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

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

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
  let p = leafTask.depends[0]; //preceding id. previous dependency
  while (true) {
    const o = a.find(o2 => o2.task === p);
    p = o.depends[0];
    if (o.depends.length === 0) { //last basecase
      return f.reverse();

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

Keep the great posts coming!

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

pentacular profile image

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.

liaowow profile image
Annie Liao Author

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