将具有本地状态的递归函数转换为使用堆栈

Question

我知道如何使用堆栈转换简单的递归函数（如所描述的here），但是，一些递归函数有一个棘手的部分，我不知道如何实现。更简单的递归函数不会更改调用者局部变量（调用者是指调用自身的函数）或者换句话说，更简单的递归函数不会根据调用自身的返回值更改其局部变量，但是当它变得棘手时它需要改变它，我不知道如何用堆栈实现做同样的事情。这是一个简化的例子：

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

如果我的问题令人困惑，只需用堆栈实现这个递归函数就可以帮助我理解我的问题。

Answer 1

您可以对堆栈使用深度优先搜索，方法是弹出最后一个元素及其父元素，如果它有子元素，则再次添加已访问的节点。 flag 阻止再次添加它。这种方法访问节点两次，一次用于搜索最深度节点，另一次用于更新 size 属性.

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

将具有本地状态的递归函数转换为使用堆栈

convert a recursive function with local state to use stack

javascript

recursion

stack

data-structures