如何停止一个正在运行的递归函数？

最编程 2024-07-20 22:30:53

...

「本文已参与好文召集令活动，点击查看：后端、大前端双赛道投稿，2万元奖池等你挑战！」

前言

前几天看到一个面试题：

请实现一个 find 函数，功能等同于 document.getElementById

分析：

就是一个查找节点函数，然后节点是可以嵌套节点的，而你是不知道会嵌套几层，正常做法是使用递归查找，直到递归到最底层。

三下五除二，刷刷刷，代码写就出来了。

代码解析

代码如下：

解法1:

function findId (id, node= document.body, map = {}) {
  const children = node.children
  for(let i = 0; i <children.length; i++) {
    if (!map[children[i].id]) map[children[i].id] = children[i]
    findId(id, children[i], map)
  }
  return map[id] || null
}

findId('header') // <div id="header"></div>
findId('header1') // 如果页面没有该元素，则return null

解析：

主要用一个对象做map，然后遍历和递归遍历把所有节点塞到map中，以id为key，节点为value，最后把需要找的id去map里面找，然后return。

解法2:

let findId = (function (findNode) {
  return function fn (id, node = document.body) {
    const children = node.children
    for (let i = 0; i < children.length; i++) {
      if (children[i].id === id) findNode = children[i]
      else findNode = fn(id, children[i])
    }
    return findNode
  }
})(null)

解析：

利用一个立即执行匿名函数，用findNode（null）做参数，然后返回一个新函数，传入id，遍历和递归遍历，如果找到该id一样的节点，就赋值给findNode, 最后返回。

下面来验证一下：

html结构：

  <div id="header">
    <div id="header-child"></div>
  </div>
  <div id="content">
    <div id="content-child">1</div>
    <div id="content-child">2</div>
  </div>
  <div id="footer">
    <div id="footer-child"></div>
  </div>

function findId (id, node= document.body, map = {}) {
  const children = node.children
  for(let i = 0; i <children.length; i++) {
    if (!map[children[i].id]) map[children[i].id] = children[i]
    findId(id, children[i], map)
  }
  return map[id] || null
}
findId('header') // <div id="header"></div>
findId('header1') // null

let findId = (function (findNode) {
  return function fn (id, node = document.body) {
    const children = node.children
    for (let i = 0; i < children.length; i++) {
      if (children[i].id === id) findNode = children[i]
      else findNode = fn(id, children[i])
    }
    return findNode
  }
})(null)
findId('header') // <div id="header"></div>
findId('header1') // null

验证通过。

真的完美吗？非也非也。

其实有个问题，你有没有发现这两个解法，都是会遍历所有节点，然后再返回节点？看下图，虽然一开始找到了header节点，但是都把剩余的节点都遍历了，然后都打印出来了

而且解法2还有个问题，正常如果有两个id一样的节点，应该是返回第一个。这里是返回的第二个。

总结以上问题：

不必要的遍历
id相同的元素应该找到第一个

正常的做法应该是如果找到对应的节点后，就应该把跳出递归函数，不应该再循环了，这样子就可以解决以上两个问题。

跳出递归

那递归函数如何跳出？

break可以吗？？？

大家知道break是在for循环，while循环中使用，恰巧我们函数有用了for循环，但是我们函数不是普通的函数，它是递归函数，函数在内部调用自己，所以它会嵌套很多层函数，你break只对那一层函数有用，其他层函数还会照样执行。所以要是要有效果，必须得在最顶层break。这样break才能break掉整个函数。

大家先看看代码：

let findId = (function (findNode) {
  return function fn (id, node = document.body) {
    const children = node.children
    for (let i = 0; i < children.length; i++) {
      if (children[i].id === id) findNode = children[i]
      if (findNode = fn(id, children[i])) break     
    }
    return findNode
  }
})(null)
findId('content-child')

针对解法2，我们做了一些改进，当我们利用递归找到findNode的时候，我们直接break，注意此时我们的break是在最顶层，这样子函数就直接执行return了，不会执行后面的函数了。

效果如下：

当然我们还可以把break改成使用return。

let findId = (function (findNode) {
  return function fn (id, node = document.body) {
    const children = node.children
    for (let i = 0; i < children.length; i++) {
      if (children[i].id === id) return children[i]
      if (findNode = fn(id, children[i])) return findNode
    }
  }
})(null)
findId('content-child')

这里原理类似，只要找到findNode，就直接在顶层return。函数就不会执行后面的了。

还有其它解法吗？

有。

当我们找到节点的时候，使用抛出异常，来中止递归函数。

以下是代码部分：

let findNode = null
try {
  function findId (id, node = document.body) {
    const children = node.children
    for (let i = 0; i < children.length; i++) {
      if (children[i].id === id) {
        findNode = children[i]
        throw new Error()
      }
      findId(id, children[i])
    }
  }
  findId('content-child')
} catch (error) {
  console.log(findNode)
}

不过我不是很推荐这种方式，因为需要在外面定义一个变量，然后还要写try-catch。

总结

以上就是自己总结的如何跳出递归函数，一般有三种方法可以实现：

break
return
抛出异常（不推荐）

大家如果有自己的见解和看法，欢迎在评论区一起交流沟通。

上一篇：简易理解： PHP中实现递归的几种方法 (学习心得，非教程) - 一、通过引用传递参数为例

下一篇：＜铁路轨道缺陷检测数据集（目标检测）

如何停止一个正在运行的递归函数？

前言

代码解析

跳出递归

总结

如何用PHP编写一个无限制级深度的递归函数来生成分类目录结构

如何用PHP实现一个简单的递归函数来计算一个数的 factorial

如何停止一个正在运行的递归函数？

Java 多线程：如何停止/中断正在运行的线程？

如何在Linux中让一个正在运行的任务转为后台执行？