convert a recursive function with local state to use stack

user_4725780 0
Viewed 96

I know how to convert simple recursive functions with a stack (like what is described here), however, some recursive functions have a tricky part that I don't know how to implement. Simpler recursive functions don't change the caller local variables (by caller I mean the function that calls itself) or in other words simpler recursive functions don't change their local variables based on the returned value from calling itself, but it becomes tricky when it needs to change that and I don't know how to do the same thing with stack implementation. Here is a simplified example:

const obj = {
  src: {
    size: 0,
    children: {
      api: {
        size: 0,
        children: {
          api_2: {
            size: 0,
            children: {
              'file1.js': {
                size: 2,
              },
              'file2.js': {
                size: 2,
              },
            },
          },
          api_1: {
            size: 0,
            children: {
              'test1.js': {
                size: 1,
              },
              'test2.js': {
                size: 1,
              },
            },
          },
        },
      },
    },
  },
};

const recursive = (object) => {
  if (object.children) {
    const currentChildren = object.children;
    Object.entries(currentChildren).forEach(([, child]) => {
      object.size += recursive(child);
    });
    return object.size;
  } else {
    return object.size;
  }
};

recursive(obj.src);

console.log(obj.src.size);
console.log(obj.src.children.api.size);
console.log(obj.src.children.api.children.api_1.size);
console.log(obj.src.children.api.children.api_2.size);

// Output: 6 6 2 4

If my question is confusing, just implementing this recursive function with a stack can help me understand my problem a lot.

recursion data-structures stack javascript
1 Answers

You could use a depth first search with a stack by popping the last element with their parent and add visited nodes again if it has children. The flag prevents to add it again. Thsi approach visits the nodes twice, one for searching for most depth node and another to update size property.

const
    update = object => {
        const
            stack = [[object]];

        while (stack.length) {
            const [o, p, flag] = stack.pop();
           
            if (!flag && o.children) {
                stack.push([o, p, true]);
                Object.values(o.children).forEach(q => stack.push([q, o]));
            } else if (p) p.size += o.size;
        }
    },
    obj = { src: { size: 0, children: { api: { size: 0, children: { api_2: { size: 0, children: { 'file1.js': { size: 2 }, 'file2.js': { size: 2 } } }, api_1: { size: 0, children: { 'test1.js': { size: 1 }, 'test2.js': { size: 1 } } } } } } } };

update(obj.src);

console.log(obj.src.size); // 6
console.log(obj.src.children.api.size); // 6
console.log(obj.src.children.api.children.api_1.size); // 4
console.log(obj.src.children.api.children.api_2.size); // 2

console.log(obj.src);
.as-console-wrapper { max-height: 100% !important; top: 0; }

user_14476750
Related