计算机算法递归

必备算法：递归！⽆论你是前端开发，还是后端开发，都需要掌握它！

递归是⼀种⾮常重要的算法思想，⽆论你是前端开发，还是后端开发，都需要掌握它。在⽇常⼯作中，统计⽂件夹⼤⼩，解析xml⽂件等等，都需要⽤到递归算法。它太基础太重要了，这也是为什么⾯试的时候，⾯试官经常让我们⼿写递归算法。本⽂呢，将跟⼤家⼀起深⼊挖掘⼀下递归算法~

什么是递归？

递归，在计算机科学中是指⼀种通过重复将问题分解为同类的⼦问题⽽解决问题的⽅法。简单来说，递归表现为函数调⽤函数本⾝。在知乎看到⼀个⽐喻递归的例⼦，个⼈觉得⾮常形象，⼤家看⼀下：

❝

递归最恰当的⽐喻，就是查词典。我们使⽤的词典，本⾝就是递归，为了解释⼀个词，需要使⽤更多的词。当你查⼀个词，发现这个词的解释中某个词仍然不懂，于是你开始查这第⼆个词，可惜，第⼆个词⾥仍然有不懂的词，于是查第三个词，这样查下去，直到有⼀个词的解释是你完全能看懂的，那么递归⾛到了尽头，然后你开始后退，逐个明⽩之前查过的每⼀个词，最终，你明⽩了最开始那个词的意思。

❞

来试试⽔，看⼀个递归的代码例⼦吧，如下：

递归的特点

实际上，递归有两个显著的特征,终⽌条件和⾃⾝调⽤: ✿ ⾃⾝调⽤：原问题可以分解为⼦问题，⼦问题和原问题的求解⽅法是⼀致的，即都是调⽤⾃⾝的同⼀个函数。

✿ 终⽌条件：递归必须有⼀个终⽌的条件，即不能⽆限循环地调⽤本⾝。

结合以上demo代码例⼦，看下递归的特点：

递归与栈的关系

其实，递归的过程，可以理解为出⼊栈的过程的，这个⽐喻呢，只是为了⽅便读者朋友更好理解递归哈。以上代码例⼦计算sum（n=3）的出⼊栈图如下：

为了更容易理解⼀些，我们来看⼀下 函数sum（n=5）的递归执⾏过程，如下：

✿ 计算sum（5）时，先sum（5）⼊栈，然后原问题sum（5）拆分为⼦问题sum（4），再⼊栈，直到终⽌条件sum（n=1）=1，就开始出栈。

✿ sum（1）出栈后，sum（2）开始出栈，接着sum（3）。

递归和遍历

递归和遍历是计算机科学中两个重要的概念。递归是一种算法，它通过将问题分解成更小的子问题来解决问题。遍历是一种算法，它通过访问数据结构中的每个元素来处理数据。

递归算法是一种自我调用的算法。它将问题分解成更小的子问题，直到问题变得足够简单，可以直接解决。递归算法通常使用函数来实现。在函数中，它会调用自身来解决更小的子问题。递归算法通常用于解决树形结构和图形结构中的问题。例如，在二叉树中查找一个元素，可以使用递归算法来遍历整个树。

遍历算法是一种访问数据结构中每个元素的算法。遍历算法通常使用循环来实现。在循环中，它会访问数据结构中的每个元素，并对每个元素执行相同的操作。遍历算法通常用于处理数组和链表等线性结构。例如，在数组中查找一个元素，可以使用遍历算法来遍历整个数组。

递归和遍历算法都有其优点和缺点。递归算法通常比遍历算法更简洁和易于理解。它可以将复杂的问题分解成更小的子问题，使得问题的解决变得更加容易。但是，递归算法可能会导致栈溢出，因为每个递归调用都会在栈中创建一个新的帧。遍历算法通常比递归算法更快，因为它不需要创建新的帧。但是，遍历算法可能会更加复杂和难以理解，因为它需要处理循环和条件语句。

在实际应用中，递归和遍历算法都有其用途。递归算法通常用于处理树形结构和图形结构中的问题，而遍历算法通常用于处理数组和链表等线性结构。在选择算法时，应该根据问题的特点和要求来选择适当的算法。

迭代算法和递归算法的区别

迭代算法和递归算法是计算机科学中常用的两种问题求解方法。虽然它们都可以用来解决相同的问题，但它们的思路和实现方式却有很大的不同。

迭代算法是一种通过重复执行一系列步骤来解决问题的方法。它通常使用循环结构来实现，每次循环都根据问题的特性进行计算和更新，直到达到预期的结果。迭代算法的特点是简单直观，容易理解和实现。它适用于问题的解决过程可以被分解为一系列可重复执行的步骤的情况。

举个例子来说明迭代算法的应用。假设我们要计算一个数的阶乘，可以通过迭代的方式来实现。首先，我们定义一个变量来保存阶乘的结果，初始值为1。然后，使用一个循环从1到该数，每次将当前结果乘以循环变量的值，最后得到阶乘的结果。

相比之下，递归算法是一种通过调用自身来解决问题的方法。它通常使用函数的递归调用来实现，每次调用都会将问题分解为更小的子问题，直到达到基本情况，然后逐层返回结果。递归算法的特点是简洁优雅，能够更好地反映问题的本质。它适用于问题的解决过程可以被分解为相同问题的不同规模的子问题的情况。

同样以计算阶乘为例，递归算法可以通过函数的递归调用来实现。首先，定义一个递归函数，该函数接收一个参数作为输入，如果输入为1，则直接返回1，否则将输入减一作为参数调用自身，然后将返回结果乘以输入，最后返回结果。

迭代算法和递归算法在实现方式和思路上有很大的不同，它们各自适用于不同类型的问题。在一些问题中，迭代算法更为直观和容易理解，而在另一些问题中，递归算法可以更好地反映问题的本质和结构。

迭代算法和递归算法在性能上也有所不同。由于递归算法需要频繁地进行函数调用和返回操作，因此在某些情况下可能会导致性能下降。而迭代算法通常可以通过优化循环结构来提高执行效率。

迭代算法和递归算法是两种常用的问题求解方法，它们各自有着不同的思路和实现方式。迭代算法通过重复执行一系列步骤来解决问题，适用于问题可以被分解为可重复执行的步骤的情况；而递归算法通过调用自身来解决问题，适用于问题可以被分解为相同问题的不同规模的子问题的情况。我们可以根据具体的问题特性选择合适的算法来解决问题，以达到更好的效果。

递归算法：

递归算法（英语：recursion algorithm）在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。递归式方法可以被用于解决很多的计算机科学问题，因此它是计算机科学中十分重要的一个概念。绝大多数编程语言支持函数的自调用，在这些语言中函数可以通过调用自身来进行递归。计算理论可以证明递归的作用可以完全取代循环，因此在很多函数编程语言（如Scheme）中习惯用递归来实现循环。

能够解决的问题：

数据的定义是按递归定义的。如Fibonacci函数。

问题解法按递归算法实现。如Hanoi问题。

数据的结构形式是按递归定义的。如二叉树、广义表等。

递归数据：

数据类型可以通过递归来进行定义，比如一个简单的递归定义为自然数的定义：“一个自然数或等于0，或等于另一个自然数加上1”。Haskell中可以定义链表为：

data ListOfStrings = EmptyList | Cons String ListOfStrings

这一定义相当于宣告“一个链表或是空串列，或是一个链表之前加上一个字符串”。可以看出所有链表都可以通过这一递归定义来达到。

尾部递归:

尾部递归是指递归函数在调用自身后直接传回其值，而不对其再加运算。尾部递归与循环是等价的，而且在一些语言（如Scheme中）可以被优化为循环指令。

不动点组合子：

即使一个编程语言不支持自调用，如果在这语言中函数是第一类对象（即可以在运行期创建并作为变量处理），递归可以通过不动点组合子（英语：Fixed-point combinator）来产生。