Javascript Question posted in
A very good W3school tutorial can be found here.

Javascript – How to optimize this algorithm using tail recursion?

I want to optimize this dfs with tail recursion,but i don’t konw how to realize it, could any help me?

My first solution is the following code, i want modify it with tail recursion to get test case with 21

const tree = {
  val: 1,
  children: [
    { val: 2, children: [] },
    {
      val: 3,
      children: [
        { val: 4, children: [] },
        { val: 5, children: [] },
      ],
    },
    { val: 6, children: [] },
  ],
};


function dfs(root) {
  if (root.children && root.children.length > 0) {
    let tmp = 0;
    for (let i = 0; i < root.children.length; i++) {
      tmp += dfs(root.children[i]);
    }
    return (tmp += root.val);
  } else {
    return root.val;
  }
}

let ret = 0;
console.log("ret: ", dfs(tree));//get 21 this case
Tags:

2

Answers


  1. 0

    You can use reduce method and arrow function to optimize.

    
function dfs(root) {
   return root.val + root.children.reduce((sum, child) => sum + dfs(child), 0);
}
    Login or Signup to reply.
  2. 0

    DFS doesn’t play nicely with tail recursion. You can hack around that, for example, by passing an explicit list of "nodes-to-visit", as in

    function sum(todo, total=0) {
    if (todo.length === 0)
        return total

    let [node, ...rest] = todo
    return sum([...rest, ...node.children], total + node.val)
}

//

const tree = {
    val: 1,
    children: [
        { val: 2, children: [] },
        {
            val: 3,
            children: [
                { val: 4, children: [] },
                { val: 5, children: [] },
            ],
        },
        { val: 6, children: [] },
    ],
};



let ret = 0;
console.log("ret: ", sum([tree])); //get 21 this case

    …but that hardly counts as an "optimization".

    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search