Annie Liao

Posted on

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

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 = [
{
},
{
depends: [ "go to the store" ]
},
{
depends: []
}
]

// -> [ 'go to the store', '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 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' ]

// -> [ 'go to the store', 'buy groceries', 'make a sandwich' ]
``````

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

``````const tasksNotInOrder = [
{
depends: [ "go to the store" ]
},
{
},
{
depends: []
}
]

// 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) {
for (let subTask of subset) {
// invoke helper function
}
}

// helper function
// base case: when we hit the task with no dependency
return
}
// recursive case:
// (2) run the function recursively with the found task
}
``````

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!

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.

for (const dependency of task.depends) {
// Schedule the task for backtracking.
return;
}
}
// Reduce the size of the problem.
}

// Take the first unordered task.
// Reduce the size of the problem, or schedule it for backtracking.
}

}

{
depends: [ "go to the store" ]
},
{
},
{
depends: []
}
];

``````

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)

@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();
}
}
};

//@perftest
const objs = genObjs(1e4);
shuffleElemsDurstenfeldMut(objs);

``````

P.S.
Keep the great posts coming!

P.S.S.
If you want the perftest code, let me know.

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.