编程笔记 html5&css&js 083 JavaScript 函数的递归

一、递归函数通常包含以下两个关键要素

1. 基本情况（Base Case）：
   这是递归的出口条件，当满足这个条件时，递归过程不再继续，并返回一个确定的结果。没有基本情况，递归函数将无休止地调用自身，导致栈溢出错误。

   例如，在计算阶乘的例子中，基本情况是当n等于0或1时，阶乘结果为1。

   function factorial(n) {
     if (n === 0 || n === 1) { // 基本情况
       return 1;
     } else {
       return n * factorial(n - 1); // 递归调用
     }
   }
   

2. 递归步骤（Recursive Step）：
   在这个阶段，函数通过调用自身来解决问题的规模更小的版本。每次递归调用都应朝着基本情况前进。

   继续使用上面的阶乘函数示例，递归步骤就是将当前n的阶乘问题转化为(n-1)的阶乘问题，直到达到基本情况。

递归的优点包括代码简洁，易于表达分治算法等复杂逻辑。但缺点是可能带来额外的系统开销，因为每次递归调用都会在内存栈中占用空间。因此，对于深度较大的递归，需要考虑优化或转换为非递归解决方案以避免栈溢出。

此外，递归函数的设计要求必须确保递归调用总是能够收敛到基本情况，否则会导致无限循环。同时，递归实现的问题应当具有“重叠子问题”的特性，即递归过程中会遇到多个相同的子问题，这样递归才能有效地利用之前计算过的中间结果，避免重复计算，这是动态规划的基础思想之一。

二、函数递归在编程中的用途

主要用于解决那些可以通过不断将问题分解为相同结构但规模更小的子问题来求解的问题。以下是递归函数的一些典型用途：

1. 数据结构遍历：

   • 树和图的遍历：例如深度优先搜索（DFS）和广度优先搜索（BFS）。对于每个节点，递归地访问其所有子节点。

     function dfs(node) {
       // 对当前节点执行操作...
       node.visited = true;
       
       for (let child of node.children) {
         if (!child.visited) {
           dfs(child); // 递归调用自身以遍历子节点
         }
       }
     }
     

2. 分治算法：

   • 排序算法：如快速排序、归并排序等，通过递归地将大数组分割成较小的数组进行排序。

     function quickSort(arr, left = 0, right = arr.length - 1) {
       if (left < right) {
         const pivotIndex = partition(arr, left, right);
         quickSort(arr, left, pivotIndex - 1); // 递归左半部分
         quickSort(arr, pivotIndex + 1, right); // 递归右半部分
       }
       return arr;
     }
     

3. 数学问题：

   • 计算阶乘、斐波那契数列、汉诺塔问题等，这些问题可以用简洁的递归来描述。

     function factorial(n) {
       if (n === 0 || n === 1) { // 基本情况
         return 1;
       } else {
         return n * factorial(n - 1); // 递归调用
       }
     }
     
     function fibonacci(n) {
       if (n <= 1) { // 基本情况
         return n;
       } else {
         return fibonacci(n - 1) + fibonacci(n - 2); // 递归调用
       }
     }
     

4. 动态规划：
   虽然动态规划通常与备忘录或自底向上的方法结合使用以优化递归实现，但递归定义仍然是很多动态规划问题的核心思路，如背包问题、最长公共子序列等。

5. 编译原理中的语法分析：
   在词法分析器和解析器中，递归下降解析器会递归地处理文法的各个产生式，用于构建抽象语法树（AST）。

递归使得代码更加简洁且易于理解，尤其对于具有自然递归性质的问题。然而，必须谨慎设计递归函数，确保它们具备正确的基本情况以及合理的递归步进逻辑，并注意避免栈溢出等性能问题。在必要时，可以使用尾递归优化或者转换为迭代方式来提高效率。

小结

函数递归属性难度较高的内容，上述示例还包括一些尚未学到的数学概念，初学简单了了解其原理即可。