在本文中，你将学习递归的工作原理。

在学习递归之前，你需要很好地理解函数的工作原理。我在本文中使用了 Python 代码作为示例，因为它的语法简单，但递归的概念对于每种编程语言都是一样的。

什么是递归？

在大多数编程语言中，一个函数可以调用另一个函数。但一个函数也可以调用自身。递归是一种函数调用自身的技术。

这是一个例子：

def call_me():
    call_me()

在这里，函数调用自身，这就是所谓的递归。

但是“调用自身”只是递归的程序定义。递归涉及将一个问题分解为更小的部分，直到无法进一步分解为止。你解决小问题并将它们组合起来以解决整个问题。

用真实生活中的例子类比递归

让我们通过一个例子来理解递归如何真正工作。

想象一下，你在迪士尼乐园排队等候，你不知道前面有多少人。

为了找出答案，你问你前面的人。

试图找出排在你前面的人数

那个人也不知道，所以她们询问她们前面的那个人。

这个过程继续进行，直到问题到达队伍最前面的人，他们看到前面没有人，回答说前面有零人。

然后队伍开始将回复传递回去。每个人在将信息传递回去之前，都会在他们被告知的数字上加 1。

当排在最前面的人回答，“前面有 0 人”时，下一个人加 1 然后回答，“前面有 1 人”，依此类推。

每个人都知道他们前面有多少人

当回复到达直接在你前面的人时，他们再加上 1 并告诉你。通过这种方式，你可以通过将前面的人给的数字添加 1，来确定你在队伍中的位置。

这个例子说明了递归如何将问题分解为更小的子问题，然后结合它们的解决方案以解决原始问题。

队伍中的每个人代表同一问题的一个较小实例：确定前面的人数。通过解决这些较小的实例并结合它们的结果，整个问题得到了解决。这正是递归的工作原理。

递归的技术细节

在编码递归时最重要的是要找出：

• 递归情况：我们可以做的最小工作。在上面的例子中，询问你前面的人他们前面有多少人是我们可以做的最小工作。

• 基本情况：无需工作的条件。在上面的例子中，队伍最前面的人没有必要问任何问题，因此这是无需工作的条件。

递归的简单例子

计算阶乘是递归的最简单例子，它将真正帮助你理解其工作原理。

有很多方法可以计算一个数的阶乘。但在这里，我们将看到递归的方式来找到它。

在思考我们如何做到这一点之前，我们需要知道一个数的阶乘是什么。

一个数的阶乘是从 1 到该数的所有数字的乘积。

例如，5 的阶乘是 120 —— 即 5×4×3×2×1。

我们还可以用数学方式表示如下：

5×(5−1)!

这意味着如果我们知道 (5−1)! 的值，我们就可以通过简单地将 5 乘以它来轻松得到阶乘。

这就是我们如何找到 4、3、2、1 和 0 的阶乘：

Factorial of 4 = 4×(4−1)!
Factorial of 3 = 3×(3−1)!
Factorial of 2 = 2×(2−1)!
Factorial of 1 = 1
Factorial of 0 = 1

通过观察这些，很明显要找到 5 的阶乘，我们必须将 5 乘以 4!。

更普遍的例子

要找到 n 的阶乘，我们需要将 n 乘以 (n−1)!。这就是你需要递归执行的过程。

现在，必须为递归设置一个停止条件。停止条件是我们不再执行其他操作的地方。当 n 是 1 或 0 时，我们可以简单地停止递归，因为这些值的阶乘是已知的。我们可以简单地说 1 的阶乘是 1，对于 0 也是如此。

因此，分解下来，要找到 n 的阶乘，所需做的最小工作量是 n×(n−1)!。当我们找到 1 或 0 的阶乘时，我们可以停止对它进行操作。

让我们看看代码是怎样的：

# 计算 n 的阶乘
def fact(n):

# 最少工作量
return n * fact(n - 1)

n = 5

# 计算阶乘
factorial = fact(n)
print(factorial)

输出:

120

让我们看看它是如何工作的：

在第一次函数调用中，计算了 5 的阶乘。接着在第二次调用中，计算了 4 的阶乘，以此类推，直到计算 2 的阶乘。

递归计算 5 的阶乘

在调用 2 的阶乘时，我们有2×fact(2−1)，即2×fact(1)。

这达到了我们的基本条件。因此，递归停止，2×fact(1)返回2×1给前一个函数调用，并且结果从堆栈中弹出。

第四次函数调用返回 2 给前一个函数调用并从堆栈中弹出

类似地，这里是其他内容的计算方式：

第三次函数调用返回 6 给前一个函数调用并从堆栈中弹出

第二次函数调用返回 24 给前一个函数调用并从堆栈中弹出

第一次函数调用返回 120 给初始函数调用并从堆栈中弹出

所以函数最终将值 120 返回给初始函数调用。

为什么我们需要一个基本条件？

在上面的例子中，我们为代码使用了停止条件。但是如果我们不添加停止条件，或者我们编写的函数永远不满足停止条件呢？

代码会永远运行吗？

不会 – 即使你不终止，代码也不会永远运行。让我们通过一个例子来理解为什么会这样。

def print_five():
    print(5)

    # 调用自身
    print_five()

# 函数调用
print_five()

输出:

5
5
5
...

RecursionError: maximum recursion depth exceeded

如果运行上面的代码，你会看到函数不会永远运行，并以消息 RecursionError: maximum recursion depth exceeded 结束。

当一个函数被调用时，它会被存储在一个调用堆栈中。下面是函数print_five()第一次被调用时在调用堆栈中的存储方式。

第一次函数调用时的调用堆栈

函数一次又一次地调用自身，并且每次调用时，函数被存储在调用堆栈中。

n 次函数调用后的调用堆栈

但是调用堆栈的大小是有限的，不能存储无限数量的函数。

调用堆栈空间不足导致栈溢出

当堆栈已满时，它无法再容纳更多调用，导致栈溢出错误。

因此，基本条件对于防止此类错误并确保递归正确终止是必不可少的。

现在让我们看看另一个例子，以便更深入地理解递归。

如何检查一个单词是否是回文

在深入代码之前，你应当知道什么是回文。回文是指正向和反向读取都相同的单词。

例如，racecar正向和反向读取都是相同的。

要检查一个单词是否是回文，我们需要检查第一个和最后一个字母是否相同。如果相同，我们接着检查第二个和倒数第二个字母是否相同。

检查 racecar 的第一个和最后一个字符是否相同

在racecar这一例子中，第一个和最后一个字母是相同的，所以我们检查第二个和倒数第二个字母是否相同。它们相同，所以现在我们检查第三个和倒数第三个字母是否相同。现在只剩下一个字母需要检查。一个单一字母始终是回文，因为它正反读都是相同的。

如何检查 racecar 是否是回文

所以，现在让我们尝试以递归的方式思考，包括最少的工作量以及确定何时不需要工作。

最少工作量

检查第一个和最后一个字母是否相同，如果相同，则移除单词中的第一个和最后一个字母。

不需要工作

当只剩下一个或没有字母时，我们可以简单地说它是一个回文。

现在，让我们看看代码是什么样子的：

# 检查回文
def check_palindrome(text):

    # 停止条件
    # 如果文本长度是 1 或 0，返回真
    if len(text) == 0 or len(text) == 1:
        return True

    # 最少工作量
    # 检查第一个和最后一个字符是否相同
    # 如果相同，移除字符串中的第一个和最后一个字符
    if(text[0]==text[-1]):
        return(check_palindrome(text[1:-1]))

# 检查字符串是否为回文
text = "racecar"
is_palindrome = check_palindrome(text)
print(is_palindrome)

以下是上述代码的工作原理：

检查 racecar 是否为回文

检查 racecar 是否为回文

何时使用递归

递归看似优雅且简单，但由于反复向堆栈添加方法带来的 CPU 开销，即便是简单问题常也需经过多个步骤方能解决。因此，在使用之前，请确保仔细考虑它是否为解决问题的正确方案。

当代码需要多个循环且显得混乱时，递归可以提供更清晰的解决方案。然而，是否使用递归取决于具体的代码以及所涉及的数据类型或数据结构。对于树和图这类数据结构，递归尤其有用。

尽管递归表面简单，但可能难以理解，即使处理简单问题也可能需要多个步骤。因此，再次提醒，一定要根据具体情况考虑使用。

总结

这只是递归的入门介绍。递归的应用场景很多，你可能对其工作原理感到困惑。我将在下一篇文章中讨论更多递归的高级示例。

顺便说一下，以下是我在学习递归过程中找到的简单且有用的资源：

• freeCodeCamp 的递归视频：我必须感谢 freeCodeCamp，他们优秀的递归视频课程在我写这篇文章时给我了极大的启发。

• Programiz Pro 的递归课程：另一个好资源是 Programiz 的递归课程。这是一个高级课程，需付费，但它经过精心设计。而且，你可以直接在他们的平台上进行练习，真的是很值得。

无论你从哪里学习，都不要花太多时间寻找完美的资源。掌握概念并开始练习——这是你唯一能真正学会的方法。

可能有数十种不同的方法可以执行此操作，但内置 reverse 方法除外，因为 JavaScript 的 String 对象上没有此方法。

以下是我解决 JavaScript 反转字符串问题的三种最有趣的方法。

算法要求

反转提供的字符串。
你可能需要将字符串转换为数组，然后才能将其反转。
你的结果必须是字符串。

function reverseString(str) {
    return str;
}
reverseString("hello");

提供测试用例

• reverseString(“hello”)  应该返回 “olleh”
• reverseString(“Howdy”)  应该返回 “ydwoH”
• reverseString(“Greetings from Earth”)  应该返回 ”htraE morf sgniteerG”

1. 使用内置方法反转字符串

对于此解决方案，我们将使用三种方法：String.prototype.split() 方法，Array.prototype.reverse() 方法和 Array.prototype.join() 方法。

• split() 方法使用指定的分隔符字符串将一个 String 对象分割成子字符串数组，以一个指定的分割字串来决定每个拆分的位置
• reverse() 方法将数组中元素的位置颠倒，并返回该数组。数组的第一个元素会变成最后一个，数组的最后一个元素变成第一个。该方法会改变原数组
• join() 方法将一个数组（或一个类数组对象）的所有元素连接成一个字符串并返回这个字符串。如果数组只有一个项目，那么将返回该项目而不使用分隔符

function reverseString(str) {
    // Step 1. Use the split() method to return a new array
    var splitString = str.split(""); // var splitString = "hello".split("");
    // ["h", "e", "l", "l", "o"]
 
    // Step 2. Use the reverse() method to reverse the new created array
    var reverseArray = splitString.reverse(); // var reverseArray = ["h", "e", "l", "l", "o"].reverse();
    // ["o", "l", "l", "e", "h"]
 
    // Step 3. Use the join() method to join all elements of the array into a string
    var joinArray = reverseArray.join(""); // var joinArray = ["o", "l", "l", "e", "h"].join("");
    // "olleh"
    
    //Step 4. Return the reversed string
    return joinArray; // "olleh"
}
 
reverseString("hello");

三个方法组合形成链式调用:

function reverseString(str) {
    return str.split("").reverse().join("");
}
reverseString("hello");

2. 用递减的 for 循环反转字符串

function reverseString(str) {
    // Step 1. Create an empty string that will host the new created string
    var newString = "";
 
    // Step 2. Create the FOR loop
    /* The starting point of the loop will be (str.length - 1) which corresponds to the 
       last character of the string, "o"
       As long as i is greater than or equals 0, the loop will go on
       We decrement i after each iteration */
    for (var i = str.length - 1; i >= 0; i--) { 
        newString += str[i]; // or newString = newString + str[i];
    }
    /* Here hello's length equals 5
        For each iteration: i = str.length - 1 and newString = newString + str[i]
        First iteration:    i = 5 - 1 = 4,         newString = "" + "o" = "o"
        Second iteration:   i = 4 - 1 = 3,         newString = "o" + "l" = "ol"
        Third iteration:    i = 3 - 1 = 2,         newString = "ol" + "l" = "oll"
        Fourth iteration:   i = 2 - 1 = 1,         newString = "oll" + "e" = "olle"
        Fifth iteration:    i = 1 - 1 = 0,         newString = "olle" + "h" = "olleh"
    End of the FOR Loop*/
 
    // Step 3. Return the reversed string
    return newString; // "olleh"
}
 
reverseString('hello');

删除注释:

function reverseString(str) {
    var newString = "";
    for (var i = str.length - 1; i >= 0; i--) {
        newString += str[i];
    }
    return newString;
}
reverseString('hello');

3. 用递归反转字符串

对于此解决方案，我们将使用两种方法：String.prototype.substr() 方法和 String.prototype.charAt() 方法

• substr() 方法返回一个字符串中从指定位置开始到指定字符数的字符.

译者注：尽管 String.prototype.substr(……) 没有严格被废弃 (as in "removed from the Web standards")，但它被认作是遗留的函数并且可以的话应该避免使用。它并非 JavaScript 核心语言的一部分，未来将可能会被移除掉。如果可以的话，使用 substring() 替代它。

'hello'.substr(1); // "ello"

• charAt() 方法从一个字符串中返回指定的字符.

'hello'.charAt(0); // "h"

递归的深度等于 String 的长度。 当 String 很长且堆栈大小是主要问题的时候，代码运行非常慢。所以此方案不是最佳解决方案

function reverseString(str) {
  if (str === "") // 如果传入空字符串，则直接返回它
    return "";
  else
    return reverseString(str.substr(1)) + str.charAt(0);
/*
递归方法的第一部分
你需要记住不会只有一次回调，会存在多次嵌套回调
每次回调的公式: str === "?"                         reverseString(str.subst(1))     + str.charAt(0)
1st call – reverseString("Hello")   will return   reverseString("ello")           + "h"
2nd call – reverseString("ello")    will return   reverseString("llo")            + "e"
3rd call – reverseString("llo")     will return   reverseString("lo")             + "l"
4th call – reverseString("lo")      will return   reverseString("o")              + "l"
5th call – reverseString("o")       will return   reverseString("")               + "o"
递归方法的第二部分
该方法达一旦到if条件，嵌套最深的调用会立即返回

删除注释:

function reverseString(str) {
    if (str === '') return '';
    else return reverseString(str.substr(1)) + str.charAt(0);
}
reverseString('hello');

使用三元表达式:

function reverseString(str) {
    return str === '' ? '' : reverseString(str.substr(1)) + str.charAt(0);
}
reverseString('hello');

JavaScript 字符串反转  是一种小型且简单的算法，在电话技术筛查或技术面试中都可能被问到。 你可以采用最简单的方式解决此问题，也可以采用递归或更复杂的解决方案来解决。

希望本篇文章对你有所帮助。 这是我的“如何解决 FCC 算法”系列文章的一部分，下面几篇文章是其他算法的了一些解决方案。

在 JavaScript 中实现重复字符串的三种方法
在本文中，我将说明如何解决 freeCodeCamp 的“重复字符串”挑战.

在 JavaScript 中判断字符串是否结束的两种方法
在本文中，我将说明如何解决 freeCodeCamp 的“确定结束”挑战.

在 JavaScript 中实现数字阶乘的三种方法
在本文中，我将说明如何解决 freeCodeCamp 的“数字阶乘”挑战”

在 JavaScript 中判断回文字符串的两种方法
在本文中，我将说明如何解决 freeCodeCamp 的“检查回文字符串”挑战”.

在 JavaScript 中查找字符串中最长单词的三种方法
在本文中，我将说明如何解决 freeCodeCamp 的“检查字符串中的最长单词”挑战”.

用 JavaScript 对句子加标题的三种方法
在本文中，我将说明如何解决 freeCodeCamp 的“字符串中每个单词首字母转为大写”挑战”.

如果你有自己的解决方案或任何建议，欢迎在评论中留言.

或者，你也可以在 Medium，Twitter，GitHub 和 LinkedIn 上关注我；-)

＃保持好奇，＃持续前进和＃实现目标！

资源

• split() method — MDN
• reverse() method — MDN
• join() method — MDN
• String.length — MDN
• substr() method — MDN
• charAt() method — MDN

原文：Three Ways to Reverse a String in JavaScript，作者：Sonya Moisset