如何理解 JavaScript 中的递归?
什么是递归?
递归一词来自"recurring",意思是一次又一次地返回。递归函数是通过逐步更改输入来一次又一次调用自身的函数。在这里,将输入改变一步意味着将输入减少或增加一步。
每当递归函数达到基本条件时,它就会停止自身的执行。让我们通过一个例子来了解什么是基本条件。例如,我们需要找到一个数字的阶乘。我们通过将输入减少 1 来调用阶乘函数,并且每当输入达到 1 时我们就需要停止。所以,这里一个作为基本条件。
语法
用户可以使用以下语法来理解 JavaScript 中的递归。
function recur(val) { if (base condition) { return; } // 执行一些操作 // 将 val 的值减少一步 return recur(newVal); }
在上面的语法中,用户可以观察到,当基本条件变为真时,我们返回 null 以停止函数的执行。如果基本条件为假,我们将使用输入值执行一些操作,并使用新的参数值再次调用 recur() 函数。
现在,让我们看看递归的各种例子。在这里,我们将学习首先使用 for 循环实现迭代算法,然后将其转换为递归方法。
示例 1(使用 for 循环查找 1 到 n 个数字的总和)
在下面的示例中,我们编写了 sumOfN() 函数来获取 1 到 N 个数字的总和。 我们使用 for 循环进行了 N 次迭代,并且在每次迭代中,我们将 I 的值添加到 sum 变量中。
最后,它返回 sum 变量的值。
<html> <body> <h3>Using the <i> iterative approach </i> to find sum of n numbers in JavaScript</h3> <div id = "content"> </div> <script> let content = document.getElementById('content'); // 使用迭代方法求 n 个数字之和的函数 function sumOfN(n) { let sum = 0; for (let i = n; i >= 1; i--) { sum += i; } return sum; } content.innerHTML += "The sum of 1 to 10 numbers is " + sumOfN(10) + "<br>"; content.innerHTML += "The sum of 1 to 20 numbers is " + sumOfN(20) + "<br>"; </script> </body> </html>
在上面的例子中,我们使用了迭代方法来求 N 个数字的总和。现在,我们将使用递归方法来做同样的事情。
示例 2(使用递归函数求 1 到 n 个数字的总和)
在下面的例子中,sumOfN() 函数是一个递归函数。我们通过将参数的值减少 1 来重复调用 sumOfN() 函数。sumOfN(N1) 返回 N-1 个数字的总和,我们将 N 添加到它以获得 N 个数字的总和。每当 N 的值变为 1 时,它都会返回 1,这是停止执行函数的基本条件。
<html> <body> <h3>Using the <i> recursive approach </i> to find sum of n numbers in JavaScript</h3> <div id = "content"> </div> <script> let content = document.getElementById('content'); // 使用递归方法求 n 个数字之和的函数 function sumOfN(n) { // 基本条件 if (n == 1) { return 1; } // 通过将 n 的值减少 1 来递归调用函数。 return n + sumOfN(n - 1); } content.innerHTML += "The sum of 1 to 10 numbers is " + sumOfN(10) + "<br>"; content.innerHTML += "The sum of 1 to 20 numbers is " + sumOfN(20) + "<br>"; </script> </body> </html>
让我们了解上述递归函数是如何工作的。下面,用户可以逐步了解递归函数调用是如何发生的。
sumOfN(5); return 5 + sumOfN(4); return 4 + sumOfN(3); return 3 + sumOfN(2); return 2 + sumOfN(1); return 1; return 2 + 1; return 3 + 3; return 4 + 6;
示例 3(迭代方法合并数组的所有字符串)
在下面的示例中,我们创建了字符串数组。我们创建了 mergeString() 函数来将数组的所有字符串合并为一个字符串。我们使用 for 循环遍历数组并将所有字符串逐一合并到"str"变量中。
<html> <body> <h3>Using the <i> iterative approach </i> to merge all strings of the array in JavaScript</h3> <div id = "content"> </div> <script> let content = document.getElementById('content'); // 使用 for 循环合并数组的所有字符串的函数 function mergeString(arr) { let str = ''; for (let i = 0; i < arr.length; i++) { str += arr[i]; } return str; } let arr = ['I', ' ', 'am', ' ', 'a', ' ', 'programmer']; content.innerHTML += "The original array is: " + arr + "<br>"; content.innerHTML += "After merging all strings of the array into the single string is " + mergeString(arr) + "<br>"; </script> </body> </html>
示例 4(使用递归方法合并数组的所有字符串)
在下面的示例中,我们将mergeString()函数转换为递归函数。我们获取数组的第一个元素,并将其与mergeString()函数返回的结果合并。mergeString()函数返回合并后的最后n-1个数组元素。此外,我们使用slice()方法从数组中删除第一个元素。
当数组中只剩下一个元素时,它会返回相同的元素,这作为基本条件。
<html> <body> <h3>Using the <i> Recursive approach </i> to merge all strings of the array in JavaScript</h3> <div id = "content"> </div> <script> let content = document.getElementById('content'); // 使用递归合并数组中所有字符串的函数 function mergeString(arr) { // 基于条件 if (arr.length == 1) { return arr[0]; } // 使用slice()方法从数组中删除第一个元素。 return arr[0] + " " + mergeString(arr.slice(1)); } let arr = ["I", "am", "a", "web", "developer"]; content.innerHTML += "The original array is: " + arr + "<br>"; content.innerHTML += "After merging all strings of the array into the single string is " + mergeString(arr) + "<br>"; </script> </body> </html>
用户应该使用哪种方法,迭代还是递归?
主要问题是迭代还是递归哪种方法更好,用户应该使用哪种方法。
在某些情况下,迭代方法比递归方法更快。此外,递归在迭代过程中占用更多内存。对于某些算法(如分治法),递归更有用,因为使用递归方法我们需要编写更少的代码。此外,如果递归方法中的基本条件未触发,用户可能会面临内存泄漏问题。
如果我们可以将代码分解成更小的部分,我们应该使用递归方法,而为了提高代码的性能,我们应该使用迭代方法。