基于JS递归函数细化认识及实用实例(推荐)

基于JS递归函数细化认识及实用实例(推荐)

什么是递归函数（Recursive Function）？

递归函数，简单来说，就是函数自己调用自己。通常情况下，递归函数都会有一个停止条件，在这个条件满足时，递归函数将不再自我调用。

实现递归函数的核心是基于函数的堆栈（Function Call Stack）机制。Javascript是一种单线程语言，所以函数调用是同步的，并且Javascript引擎使用函数的堆栈来保留当前函数的执行状态，以便接下来再恢复它的执行。

递归函数的应用场景

递归函数通常应用在以下场景：

• 迭代对象或数组
• 解决问题的分治法策略
• 遍历树形结构(如：DOM树)
• 等等...

如何实现递归函数？

在Javascript中实现递归函数，需要考虑两点：

• 入口参数（Entry Parameter）：指进入递归函数时所传入的参数。
• 停止条件（Exit Condition）：指在某种情况下，递归函数会停止调用自身的条件。这种停止调用的条件非常重要，否则递归调用将永远不会停止。

下面是一个简单的例子，用来演示递归函数的基本使用：

function factorial(n) {
  if (n === 1) return 1; // 停止条件，当 n = 1 时停止
  return n * factorial(n - 1); // 递归调用自己
}

console.log(factorial(5)); // 输出 120 (因为 5*4*3*2*1 = 120)

在此例中：

• 入口参数是 n 。
• 停止条件是当 n 变为 1 时。

这个例子用递归方式计算并返回 n 的阶乘。

如何应用递归函数？

实例一： 斐波那契数列

斐波那契数列，指的是从 0,1 开始，任意两个相邻的数值相加而得到的一个新的数值。数列的前两项是 0 和 1 ，其他项则由前两项之和拼接而成。

以下是使用递归函数计算第 n 项斐波那契数值的一份代码：

function fibonacci(n) {
  if (n === 1 || n === 2) return 1; // 停止条件
  return fibonacci(n - 1) + fibonacci(n - 2); // 递归调用自己
}

console.log(fibonacci(6)); // 输出 8 (因为第六项数值为 0、1、1、2、3、5、8)

在此例中：

• 入口参数是 n。
• 停止条件是当 n 为 1 或 2 时。
• 递归式则是斐波那契数列的公式：fibonacci(n) = fibonacci(n - 1) + fibonacci(n - 2)。

实例二：获取树形结构中所有的叶子节点

递归函数在处理树形结构数据时，是非常有用的。例如，我们可以使用递归函数来遍历树形结构，并获取其所有的叶子节点。

以下是一个简单的例子：

const tree = {
  label: '1',
  children: [
    { label: '1-1' },
    {
      label: '1-2',
      children: [
        { label: '1-2-1' },
        { label: '1-2-2' }
      ]
    },
    { label: '1-3' }
  ]
};

function getLeafNodes(node) {
  if (!node.children || !node.children.length) return [node.label];
  return node.children.map(getLeafNodes).reduce((pre, cur) => pre.concat(cur));
}

console.log(getLeafNodes(tree)); // 输出 ['1-1', '1-2-1', '1-2-2', '1-3']

在此例中：

• 入口参数是树形结构中的一个节点node。
• 停止条件是节点node不存在子节点或其子节点数为0。
• 递归式则是通过map函数调用其他所有子节点，最后使用reduce将所有子节点得到的数据合并成一个展开的数组。

通过这个例子我们可以看到，使用递归函数遍历树形结构时，可以非常方便的获取到其子节点中的所有数据。

总结

递归函数是Javascript中非常有用的工具之一，在很多场景下都能起到非常重要的作用。掌握递归函数的原理和使用方法，可以帮助我们更好的解决各种复杂的问题。