Discussion on: When Recursion Comes to Rescue

[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.

[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.

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