递归的概述

摘取维基百科关于递归的描述：递归（英语：Recursion），又译为递回，在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。递归一词还较常用于描述以自相似方法重复事物的过程。例如，当两面镜子相互之间近似平行时，镜中嵌套的图像是以无限递归的形式出现的。也可以理解为自我复制的过程。

举个语言例子：

大雄在房里，用时光电视看着从前的情况。电视画面中的那个时候，他正在房里，用时光电视，看着从前的情况。电视画面中的电视画面的那个时候，他正在房里，用时光电视，看着从前的情况……

伪代码：

func1() {
  大雄在房里，用时光电视看着从前的情况。电视画面中的那个时候，他正在房里，用时光电视，看着  从前的情况。电视画面中的电视画面的那个时候，他正在房里，用时光电视，看着从前的情况……
  func1()
}

程序员眼中的递归

递归是指在函数的定义中使用函数自身的方法。

递归有两层含义：

递归问题必须可以分解为若干个规模较小、与原问题形式相同的子问题。并且这些子问题可以用完全相同的解题思路来解决；
递归问题的演化过程是一个对原问题从大到小进行拆解的过程，并且会有一个明确的终点（临界点）。一旦原问题到达了这个临界点，就不用再往更小的问题上拆解了。最后，从这个临界点开始，把小问题的答案按照原路返回，原问题便得以解决。

这里举个用递归求n的阶乘的例子：

上代码：

func factorial(_ n: Int)->Int {
      if 1 == n {
          return n;
      } else {
          return factorial(n-1) * n
      }       
 }

这里n传入5，把式子展开如下：

factorial简化为f

factorial(5)
=> 5 * f(4)
=> 5 * f(4 * f(3))
=> 5 * f(4 * f(3 * f(2)))
=> 5 * f(4 * f(3 * f(2 * f(1))))
=> 5 * f(4 * f(3 * f(2 * 1))
=> 5 * f(4 * f(3 * 2))
=> 5 * f(4 * 6)
=> 5 * 24
=> 120

图形简化如下：

image.png

看图理解递归就是，先一步步往下递，然后回归，回归的起点就是达到终止条件的时候。

递归的基本思想就是把规模大的问题转化为规模小的相同的子问题来解决。 在函数实现时，因为大问题和小问题是一样的问题，因此大问题的解决方法和小问题的解决方法也是同一个方法。这就产生了函数调用它自身的情况，这也正是递归的定义所在。

用递归解决问题的函数必须有明确的结束条件，否则就会导致无限递归的情况。总结起来，递归的实现包含了两个部分，一个是递归主体，另一个是终止条件。

递归的算法思想

递归的数学模型其实就是数学归纳法，这个证明方法是我们高中时期解决数列问题最常用的方法。接下来，我们通过一道题目简单回顾一下数学归纳法。

一个常见的题目是：证明当 n 等于任意一个自然数时某命题成立。

当采用数学归纳法时，证明分为以下 2 个步骤：

证明当 n = 1 时命题成立；
假设 n = m 时命题成立，那么尝试推导出在 n = m + 1 时命题也成立。

与数学归纳法类似，当采用递归算法解决问题时，我们也需要围绕这 2 个步骤去做文章：

当你面对一个大规模问题时，如何把它分解为几个小规模的同样的问题；
当你把问题通过多轮分解后，最终的结果，也就是终止条件如何定义。

所以当一个问题同时满足以下 2 个条件时，就可以使用递归的方法求解：

可以拆解为除了数据规模以外，求解思路完全相同的子问题；
存在终止条件。

递归的案例

1，前序遍历二叉树，如下图所示：

image.png

解题步骤:

对树中的任意结点来说，先打印这个结点，然后前序遍历它的左子树，最后前序遍历它的右子树。

代码如下：

func preOrderTraverse(_ root: TreeNode?) {
    //终止条件
    guard let rt = root else {
        return
    }

    //遍历步骤
    print("node:(rt.val)")
    preOrderTraverse(rt.left)
    preOrderTraverse(rt.right)
}

2，汉诺塔问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着 64 片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上，并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

解题步骤:

假设 n = 1,只有一个盘子，很简单，直接把它从 A 中拿出来，移到 C 上；

如果 n = 2 呢？这时候我们就要借助 B 了，因为小盘子必须时刻都在大盘子上面，共需要 4 步。

0806.gif

如果 n > 2 呢？思路和上面是一样的，我们把 n 个盘子也看成两个部分，一部分有 1 个盘子，另一部分有 n - 1 个盘子。

08061.gif

那 n - 1 个盘子是怎么从 A 移到 C 的呢？

注意，当你在思考这个问题的时候，就将最初的 n 个盘子从 A 移到 C 的问题，转化成了将 n - 1 个盘子从 A 移到 C 的问题，依次类推，直至转化成 1 个盘子的问题时，问题也就解决了。这就是分治的思想。

而实现分治思想的常用方法就是递归。不难发现，如果原问题可以分解成若干个与原问题结构相同但规模较小的子问题时，往往可以用递归的方法解决。具体解决办法如下：

n = 1 时，直接把盘子从 A 移到 C；
n > 1 时，
- 先把上面 n - 1 个盘子从 A 移到 B（子问题，递归）；
- 再将最大的盘子从 A 移到 C；
- 再将 B 上 n - 1 个盘子从 B 移到 C（子问题，递归）。

代码如下：

class Solution {
   func hanota(_ A: inout [Int], _ B: inout [Int], _ C: inout [Int]) {
        
        let n = A.count
        move(n, &A, &B, &C)

    }
    
    func move(_ n:Int,_ A: inout [Int], _ B: inout [Int], _ C: inout [Int])       {
          if n == 1{
              C.append(A[A.count-1])
              A.removeLast()
              return
          }
          else{
              move(n-1,&A, &C, &B)

              C.append(A[A.count-1])
              A.removeLast()

              move(n-1,&B, &A, &C)
          }
    }
    
}