javascriptdepth-first-searchtail-recursion

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


Solution

  • 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".