递归和循环遍历

这两天在思考一个问题，就是关于递归和循环遍历哪一个性能更好？以及项目中是否应该使用循环遍历替换掉递归函数？？ 带着这样的疑问网上搜了一下，总结如下：

递归函数的优点

代码简洁； 结构清晰，可读性强； 符合逻辑思维的习惯，更容易理解；

递归函数的缺点

递归层次太深，存在栈溢出的可能；

JS循环的优点

效率高，运行时间只因循环次数增加而增加；

JS 循环的缺点

不容易理解，编写复杂问题时困难。代码可读性不如递归；

很明显，这样的答案是不能满足我的需求的。下面我根据自己在项目中的实践来和大家探讨和分析。

学习递归函数

// 斐波拉契数列
function fn(n) {
  function inner(n, result) {
    if (n === 1) {
      return result;
    } else {
      const [ v1 = 0, v2 = 0 ] = result.slice(-2);
      result.push(v1 + v2);
      return inner(n - 1, result);
    }
  }
  return inner(n, [1]);
}

// 求和
function sum(n) {
  function inner(n, result) {
    if (n === 1) {
      return result;
    } else {
      return inner(n - 1, result + (n - 1));
    }
  }
  return inner(n, n);
}

// 阶乘
function multiply(n) {
  function inner(n, result) {
    if (n === 1) {
      return result;
    } else {
      return inner(n - 1, result * (n - 1));
    }
  }
  return inner(n, n);
}

我的思考：

以上三个递归函数在平常学习中非常的常见，但是实际项目中非常少见，这是因为这些都太简单了，实际应用中很少遇到；

仔细观察，你还会发现上面三个递归函数都是尾递归，

浏览器对尾递归有优化策略：在调用链上可以做到只有一个函数在使用栈，只存在一个调用帧，永远不会发生栈溢出；

浏览器对尾递归的支持有限，目前仅有个别浏览器支持（safair），主流浏览器还不支持 查看；

更重要的是，实际的应用中，很少有机会写出尾递归的情况。

真实案例分析

案例一，在树结构中通过目标节点的 key 查找其所有的父节点 key 的集合

type TreeNode = {
  key: string;
  parentKey: string;
  children?: TreeNode[];
};

// 使用递归函数
export function getParentKeys(tree: TreeNode, id: string) {
  if (!tree) return [];
  // 标识，通过该标识来判断是否已经在树中找到了目标节点，一旦找到了目标节点，就停止递归查找。
  let hasFind = false;
  // 所有父节点的 key 的集合
  const parentKeys: string[] = [];

  function inner(node: TreeNode) {
    // 如果已经找到了，则停止继续查找
    if (hasFind) return;

    const { key, parentKey, children = [] } = node;
    // 如果当前节点的 key 与 目标 id 一致，则停止查找，并更新 hasFind
    if (key === id) return hasFind = true;

    /**
     * 每遍历一个节点，我们都将该节点的 key push 到 parentKeys 集合中；
     * 并在该节点（含该节点下的所有子孙节点）遍历结束后，再将该节点从 parentKeys 集合中 pop 掉；
     * 通过这种方式你会发现，如果该节点作为根节点，那么当没有找到与 id 匹配的节点时，该节点以及所有的子孙节点的 key 都将从 parentKeys 集合中 pop 掉；
     * 另一种情况，当该节点下的某个直接子节点的 key 与 id 匹配，那么 parentKeys 集合中的最后一项就是该节点的 key。
     */
    parentKeys.push(node.key);

    for (let i = 0; i < children.length; i++) {
      inner(children[i]);
    }

    !hasFind && parentKeys.pop();
  }

  inner(tree);
  return parentKeys;
}

上面的这个案例，我在封装 Antd 的 Tree 组件时遇到了这种需求。上面的递归函数其实已经可以满足我的实际需要了。 但有些时候我们应该考虑一些特殊情况，例如树的层级、分支特别多的情况（实际应用中，树的层级一般都是有限的，所以很少有那么大的数据，导致递归函数调用时栈溢出的情况），不过这种情况还是要考虑的。下面我们来看看通过循环遍历如何实现。

// 使用循环遍历
function getParentKeys(tree: TreeNode | TreeNode[], id: string) {
  if (!tree) return [];

  const parentKeys: string[] = [];
  // 拷贝一份 tree，避免对源对象进行修改
  const stack = Array.isArray(tree) ? [...tree] : [tree];

  /**
   * 使用深度优先遍历的方法进行查找
   * 每次遍历节点时，都需要对 parentKeys 集合的最后一项 lastKey 进行验证，是否与当前节点的 parentKey 相等；
   * 如果 lastKey 与当前节点的 parentKey 不相等，那么就 pop() 掉 lastKey，直到满足条件；
   * 这种情况一般出现在一条分支遍历结束后，并开始遍历其他分支的节点（例如：祖先节点是同一个节点，如图一中 B ==> C）时才会出现。
   */
  while (stack.length) {
    const { key, children = [], parentKey } = stack.shift()!;
    while (parentKeys.length) {
      if (parentKeys[parentKeys.length - 1] === parentKey) {
        break;
      } else {
        parentKeys.pop();
      }
    }

    // 如果当前树节点的 id 与目标节点的 id 相等，则直接返回 parentKeys，并中断遍历。
    if (key === id) return parentKeys;

    let len = children.length;

    len > 0 && parentKeys.push(key);

    while (len--) {
      stack.unshift(children[len]);
    }
  }
  return parentKeys;
}

图一：

案例二，对树结构数据进行遍历，并将匹配的内容的进行颜色渲染

图二：

// 对匹配的文本进行着色
function formatTitle(title: string, filterText: string) {
  let newTitle = title;

  if (title.indexOf(filterText) >= 0) {
    newTitle = [];
    const ary = title.split(filterText);
    const length = ary.length;

    for (let i = 0; i < length; i++) {
      ary[i] && newTitle.push(ary[i]);
      if (i < length - 1) {
        // 相邻的两个元素之间才会添加
        newTitle.push(<span style={{ color: 'red' }} key={i}>{filterText}</span>);
      }
    }

    newTitle = <span>{newTitle}</span>;
  }
  return newTitle;
}

// 使用递归函数
function computedTree(tree: TreeNode[], filterText) {
  return tree.map(item => {
    const { key, parentKey, title, children } = item;

    return {
      key,
      parentKey,
      title: formatTitle(title, filterText),
      children: children?.length > 0 ? computedTree(children, filterText) : null,
    };
  });
}

使用递归函数的代码比较简单，也符合我们的思维习惯。 项目中使用 Antd 的 Tree 组件时，需要根据条件将节点的颜色进行着色，这里就必须对每个节点进行遍历，然后将 title 通过 formatTitle() 函数进行处理，就可以得到我们想要的内容。

// 使用循环遍历
function computedTree(tree: TreeNode[], filterText: string) {
  const root = [];
  const parentNodes = [];
  const stack = Array.isArray(tree) ? [...tree] : [tree];

  /**
   * 使用深度优先遍历的方法进行遍历
   * 每次遍历节点时，都需要对 parentNodes 集合的最后一项 last 进行验证，是否为当前节点的 parentNode；
   * 如果 last 不是当前节点的 parentNode，那么就 pop() 掉 last，直到满足条件；
   * 这种情况一般出现在一条分支遍历结束后，并开始遍历其他分支的节点（例如：祖先节点是同一个节点，如图一中 B ==> C）时才会出现。
   * 找到当前节点的父节点，并将当前节点的副本添加到其父节点的 children 集合中的。
   */
  while (stack.length) {
    let currentParent = null;
    const { key, parentKey, title, children = [] } = stack.shift();

    while (parentNodes.length) {
      const last = parentNodes.slice(-1)[0];
      if (last.key === parentKey) {

        currentParent = last;
        break;
      } else {
        parentNodes.pop();
      }
    }

    const item = { key, parentKey, title: formatTitle(title, filterText) };

    // 如果 currentParent 不存在，说明当前节点就是根节点，此时我们只要将节点添加到 root 集合中即可。
    if (currentParent) {
      if (!currentParent.children) currentParent.children = [];
      currentParent.children.push(item);
    } else {
      root.push(item);
    }

    let length = children.length;

    if (length > 0) parentNodes.push(item);

    while (length--) {
      stack.unshift(children[length]);
    }
  }
}

总结

两个案例实践下来，发现将递归转换成循环遍历的方式有时需要申请一个额外的内存空间才能完成，这其实就是利用空间换时间。

案例一中，将父节点的 key 存放在一个可存取的变量中，按照固定的逻辑进行存取和释放从而达到我们的目的。案例二与案例一也是类似的。

对比递归函数，我认为循环遍历它的逻辑复杂度更高。并且经过测试发现，在相同条件测试时，采用递归函数的方式耗时更短。

如果从设计简单、数据量不大的层面考虑，认为递归函数完全可以满足一般项目的的需求。

然而，从栈溢出的方面考虑，循环遍历更优一些。与此同时，我们需要考虑到另一个问题，就是循环遍历有时需要借助内存空间，内存被占用也会导致性能下降。

最后，还是那句老话，技术没有绝对的好和坏。技术的选择最终还是取决于开发者自身，取决于需求的定义。当下能满足的就是最好的。