How to optimize this algorithm using tail recursion?

Question

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

Answer 1

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

Answer 2

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

Answer 3

Most JavaScript engines do not currently implement tail call optimisation, but if you really want a tail call, and it must be depth-first order, then you will need to mimic the iterative algorithm, and pass a stack reference to the tail call.

Here is a recursive function with a tail call that performs a pre-order traversal. It uses the stack to keep track of the current indices in each of the unfinished children arrays.

const preorder = ({val, children}, stack=[], sum=0) => {
    let i = 0;
    if (!children?.length) {
        if (!stack.length) return sum + val; // Last value in preorder sequence
        [children, i] = stack.splice(-2); // Get next sibling: children[i]
    }
    if (i + 1 < children?.length) stack.push(children, i + 1);
    return preorder(children[i], stack, sum + val);
}


// Example tree
const tree = {val: 1,children: [{ val: 2, children: [] },{val: 3,children: [{ val: 4, children: [] },{ val: 5, children: [] },],},{ val: 6, children: [] },],};
console.log(preorder(tree));