将递归转换成循环

递归二字可谓相当传神。“递”表示递进，嵌套。“归”表示返回。递归调用一定要有一个临界点用于判断返回。

举个例子，获得如下数据结构，值不为对象的路径数组（顺序无关）。

{
  a: {
    b: {
      c: {
        d: {
          e: 1,
          f: '2',
        },
        g: true,
      },
    },
  },
};
//返回[ 'a/b/c/d/e', 'a/b/c/d/f', 'a/b/c/g' ]

写成递归，大抵如下:

function getFilePaths(obj) {
  const filePaths = [];

  function checkFolder(folder, keyPath) {
    Object.keys(folder).forEach((key) => {
      const value = folder[key];
      if (Object.prototype.toString.call(value) === '[object Object]') {
        checkFolder(value, [...keyPath, key]);
      } else {
        filePaths.push([...keyPath, key].join('/'));
      }
    });
  }

  checkFolder(obj, []);

  return filePaths;
}

我们知道函数调用形成帧，帧放在栈里。递归是一种特殊的、重复的函数调用。借用调用栈的思想，所有的递归都可以改成循环的形式。

function getFilePaths(folder) {
  const stack = [];
  const filePaths = [];

  stack.push({
    folder,
    keyPath: [],
  });

  while (stack.length > 0) {
    const frame = stack.pop();
    const { folder, keyPath } = frame;

    Object.keys(folder).forEach((key) => {
      const value = folder[key];
      if (Object.prototype.toString.call(value) === '[object Object]') {
        stack.push({
          folder: value,
          keyPath: [...keyPath, key],
        });
      } else {
        filePaths.push([...keyPath, key].join('/'));
      }
    });
  }

  return filePaths;
}

必须要说的是，把代码写成直觉上的第一反应。也就是说递归绝大多数要写成递归的形式，除非有call stack overflow问题。 不要过早把本应写成递归的，改写成循环。