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

Most JavaScript engines don’t have tail call elimination, so note that this won’t be an optimization. Also, DFS isn’t really suited to tail calls – you may as well just use an array as a stack with a loop if that’s what you were going to do with tail recursion. — Ry-
– Ry- ♦, Commented Jan 14, 2024 at 7:39

trincot · Accepted Answer · 2024-01-14 22:19:12Z

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

gog · Accepted Answer · 2024-01-14 09:24:14Z

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

answered Jan 14, 2024 at 9:24

gog

11.4k2 gold badges29 silver badges42 bronze badges

1 Comment

trincot Over a year ago

This is quite memory intensive, each newly created array passed as argument being referenced from the call stack until the end. Recreating arrays at every call costs time too.

Top Dev · Accepted Answer · 2024-01-14 07:40:01Z

-1

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

answered Jan 14, 2024 at 7:40

Top Dev

11 bronze badge

1 Comment

Ry- Over a year ago

Definitely cleaner, but not a tail call (or really an optimization).

Collectives™ on Stack Overflow

How to optimize this algorithm using tail recursion?

3 Answers 3

Comments

1 Comment

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related