函数调用自身称为递归(Recursion)，在计算机科学指将问题分解为同类的子问题来解决的方法。

分治(Divide and Conquer)，指将问题分而治之，通过分成多个子问题来简化求解，最终将子问题的解合并成原问题的解。分治的代码一般是递归形式的。

递归

递归的一般形式如下：

int func(传入数值) {
  if (终止条件) return 最小子问题解;
  return func(缩小规模);
}

比如使用递归来实现快速排序：

void quickSort(int a[], int left, int right) {
    if(left >= right) {
        return;
    }
    int mid = partition1(a, left, right);
    quickSort(a, n, left, mid-1);
    quickSort(a, n, mid+1, right);
}

当发现问题可以被分解成相同的小问题时，就可以尝试通过递归来解决。

递归通过栈来实现，使用时需要注意栈溢出问题，也就是递归的层数不能太多，如果层数非常多，则要考虑转成循环来实现，递归转循环一般也需要借助栈。

有时候递归求解的子问题可能会被重复求解，这时可以通过记忆化递归来优化，所谓记忆化递归就是保存已解决的子问题的结果，在遇到相同的子问题时直接使用之前保存结果。当然，也可以对递归本身进行优化，减少不必要的计算。

递归示例：

  • 汉诺塔问题 - 力扣（LeetCode）
  • 汉诺塔 - 维基百科，自由的百科全书

    • 有三根杆子A，B，C。A杆上有 N 个 (N>1) 穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至 C 杆：
        1.每次只能移动一个圆盘；
        2.大盘不能叠在小盘上面。
      提示：可将圆盘临时置于 B 杆，也可将从 A 杆移出的圆盘重新移回 A 杆，但都必须遵循上述两条规则。
      问：如何移？最少要移动多少次？

    • 思路：假设有 A、B、C 三个塔，A 塔有N 块盘，目标是把这些盘全部移到 C 塔。那么先把 A 塔顶部的N-1块盘移动到 B 塔，再把 A 塔剩下的大盘移到 C，最后把 B 塔的 N-1 块盘移到 C。

      #include <iostream>
using namespace std;

void Towers(int n, char a, char b, char c) {
    if (n == 1) {
        cout << "Move disk " << n << " from " << a << " to " << c << endl;
    } else {
        Towers(n - 1, a, c, b);
        cout << "Move disk " << n << " from " << a << " to " << c << endl;
        Towers(n - 1, b, a, c);
    }
}

int main(int argc, char *argv[]) {
    int n;
    cin >> n;
    Towers(n, 'A', 'B', 'C');
    cout << endl;
}


分治

分治算法的基本流程：分解->解决->合并。 

  1. 分解原问题为结构相同的子问题。
  2. 分解到某个容易求解的边界之后，进行递归求解。
  3. 将子问题的解合并成原问题的解。

分治法能解决的问题一般有如下特征：

  • 该问题的规模缩小到一定的程度就可以容易地解决。
  • 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质，利用该问题分解出的子问题的解可以合并为该问题的解。
  • 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

典型的分治算法应用是归并排序，其代码流程如下：

void merge_sort(一个数组) {
  if (可以很容易处理) return;
  merge_sort(左半个数组);
  merge_sort(右半个数组);
  merge(左半个数组, 右半个数组);
}

分治示例：







  • 无标签