# 递归

递归的基本思想：把规模较大的原问题拆解成，规模较小，并且结构与原问题相同的子问题。

 下图就展现了递归的思想：

# 如何写递归代码

我们可以用递归来定义函数。在开始写函数之前我们需要先给出 递归定义：

• 基本步骤 ( 终止条件 )：定义终止条件，当符合时表示进入了最底层。
• 递归步骤：从下一层的结果得到当前层结果的步骤。

当有了递归定义后， 我们再把它转化成递归代码。

下面举两个例子：

// 当有 n 个台阶时，走法等于 n - 1 个台阶的走法加上 n - 2 个台阶的走法。
f(n) = f(n - 1) + f(n - 2)

f(1) = 1
f(2) = 2

int f(int n) {

  // 基本步骤（终止条件）
  if (n == 1) return 1;
  if (n == 2) return 2;

  // 递归步骤（递归公式）
  return f(n-1) + f(n-2);
}

f(0) = 1;
f(1) = 1;

f(n) = n * f(n - 1);

int factorial(int n) {
  if(n <= 1) return 1;
  return n * factorial(n - 1);
}

# 递归代码模板

下面的递归模板可以看作是对于上面思想的细化，实际应用起来更简单。

第 2 - 5 步都可以看作是对于 递归步骤 的拆解。

public void recursion(int param) {

  // 1. 递归终止条件
  if(param ?) {
    process(result)
    return result;
  }

  // 2. 处理传递给下一层的参数
  process(param);

  // 3. 进入到下一层
  result = recursion(params);

  // 4. 可能需要在当前层结束之前，有些东西要处理
  process(status);

  // 5. 处理下一层返回的结果，然后返回给上一层
  return process(result);
}

# 将递归代码改写为非递归代码

虽然递归算法的表达力很强，但是递归算法的空间复杂度高、有堆栈溢出的风险、存在重复计算、过多的函数调用会耗时较多等问题。所以，在开发过程中，我们要根据实际情况来选择是否需要用递归的方式来实现。

比如 👆 走台阶的的例子中，就会出现重复计算的问题。想要计算 f(5)，需要先计算 f(4) 和 f(3)，而计算 f(4) 还需要计算 f(3)，因此，f(3) 就被计算了很多次，这就是重复计算问题。

可以用 迭代循环 去改写成非递归写法。

例如，上面走台阶的递归算法可以改写成：

int f(int n) {
  if (n == 1) return 1;
  if (n == 2) return 2;

  int result = 0;
  int pre = 2;
  int prepre = 1;
  for (int i = 3; i <= n; ++i) {
    result = pre + prepre;
    prepre = pre;
    pre = result;
  }
  return result;
}

# 递归树

# 什么是递归树

借助递归树，我们可以分析递归算法的时间复杂度

前面讲过，递归的思想就是，将大问题分解为输入规模更小的同样问题。这样一层一层地分解，直到问题的数据规模被分解得足够小，不用继续递归分解为止。

如果把分解过程画成图，就像是一棵树，可以被称作递归树。

下图就是斐波那契数列的递归树。节点里的数字表示数据的规模，一个节点的求解可以分解为左右子节点两个问题的求解。

# 用递归树来求解时间复杂度

下面展示如何用递归树来分析 “递归排序算法” 的时间复杂度。

归并排序每次会将数据规模一分为二。我们把归并排序画成递归树，就是下面这个样子：

• 每次递归，数组都会被一分为二，时间上的消耗记作常量 1；
• 比较耗时的是归并操作，也就是把两个子数组合并为大数组；
• 从图中我们可以看出，每一层归并操作消耗的时间总和是一样的，跟要排序的数据规模有关。操作消耗的时间记作 n；
• 现在，我们只需要知道这棵树的高度 h，用高度 h 乘以每一层的时间消耗 n，就可以得到总的时间复杂度 $O(n ∗ h)$。
• 可以看出来，归并排序递归树是一棵满二叉树。满二叉树的高度大约是 $log_2​n$，所以，归并排序递归实现的时间复杂度就是 $O(nlogn)$。

# 实战一：分析快速排序的时间复杂度

# 实战二：分析斐波那契数列的时间复杂度

int f(int n) {
  if (n == 1) return 1;
  if (n == 2) return 2;
  return f(n-1) + f(n-2);
}

我们先把上面的递归代码画成递归树，就是下面这个样子：

• $​f(n)$​ 分解为 $​f(n−1)$​ 和 $​f(n−2)$​，每次数据规模都是 $​−1$​ 或者 $​−2$​，叶子节点的数据规模是 $​1$​ 或者 $​2$​；
• 所以，从根节点走到叶子节点，每条路径是长短不一的。如果每次都是 $​−1$​，那最长路径大约就是 $​n$​；如果每次都是 $​−2$​，那最短路径大约就是 $n/2$​；
• 每次分解之后的合并操作只需要一次加法运算，我们把这次加法运算的时间消耗记作 $1$；
• 从上往下，第一层的总时间消耗是 $1$，第二层的总时间消耗是 $2$，第三层的总时间消耗就是 $2^2$。依次类推，第 $k$ 层的时间消耗就是 $2^{k−1}$；
• 那整个算法的总的时间消耗就是每一层时间消耗之和；
  • 如果路径长度都为 $n$，那这个总和就是 $2^n−1$；
  • 如果路径长度都是 $n/2$ ，那整个算法的总的时间消耗就是 $2^{n/2}​-1$；
• 所以，这个算法的时间复杂度就介于 $O(2^n)$ 和 $O(2^{n/2}​)$ 之间。

虽然这样得到的结果还不够精确，只是一个范围，但是我们也基本上知道了上面算法的时间复杂度是指数级的，非常高。