分治是一种思想，递归是实现分治的手段之一。
**

分治思想与递归方法

以下只是个人的理解，有意把分治与递归不划等号，可能与网上大多数说法不一致，若读者认为不合适，大可不必读完。
分治即“分而治之”，从字面上来理解，就是把一个问题分为几个子问题，通过求解子问题（如果子问题仍然不好求解，则继续分解，直至分成一个答案显而易见的小问题）来得到原问题的解。
递归的定义大概是一个函数自己调用自己来解决问题的一种方法。而一个函数所能解决的问题是固定的，因此递归能解决的问题有一种特征：原问题能够分解为多个与原问题相同或相似的子问题，随着进一步分解，问题能够分解为一个答案显而易见的小问题。
通过以上两种说法，不难发现分治的范围更广，它不要求子问题要与原问题相似，而递归则有这个要求。这对应我们编程中，一个复杂的问题，我们按点拆分为几个较为简单的函数来解决（这也是分治，此时往往分解程度不深，子问题之间的相似度可能也不高）；而当一个复杂的问题能够分解若干相同或相似的子问题时（此时往往由于分解程度会很深，子问题数量会很多，不再适合手写那么多函数），恰好符合递归函数的要求，因此可以用递归来解决。

相同处：

  1. 子问题的规模比原问题更小，且子问题之间互不影响。

  2. 都要求能够拆分到答案显而易见的小问题。

    递归方法

    分治思想的重点在于三个字：“分”，“治”，“合”。

  3. 分：将问题分解为规模更小的子问题。

  4. 治：将这些规模更小的子问题逐个击破。
  5. 合：将已解决的子问题合并，最终得出“母”问题的解。

递归的思路与分治相似，只不过在“治”的阶段，递归采用自己调用自己的方式解决子问题，分治则可能使用完全不同的若干函数解决。

于我个人而言，在实际应用中，递归的最难点在于“分”，即如何把原问题分解为若干相似的子问题。因为只有明白了如何划分子问题，才能明白自己的递归函数要解决的问题是什么（传什么参，返回什么结果）。

递归 4 要素：

  1. 划分子问题。发挥自己的才智，设法把原问题拆分成若干相同或相似的子问题。
  2. 正确定义递归函数。关注函数参数是什么，返回是什么，而不必深入了解递归的详细过程。即把递归函数当做普通函数使用，我给它正确传参，它就会给我返回正确的结果。
  3. 确定递归出口：寻找问题的基例，即随着问题的分解，能不能找到一个答案显而易见的小问题。
  4. 合并子问题的解：通过把子问题的解合并起来得到原问题的解，难点在于“合并”。

递归举例

归并排序

著名的归并排序和快速排序便是经典的递归算法，这里详细讲解一下归并排序。
以对整数序列进行升序排序为例，nums= [8, 2, 1, 9, 6, 4, 3, 7]。
归并排序的算法思想：

  1. 不断对半拆分数组，直至所有子数组的长度为 1。
  2. 然后两两合并子数组得到一个有序序列。

接下来看看归并排序是如何体现分治思想的：
image.png
而我们又恰好发现，每一次“分”和“合”的过程都是相同的，而且如果数组规模很大的话，这两个过程会大量重复，这恰好符合递归的要求，因此考虑用递归解决。
简单代码实现如下：

  1. package main
  3. import (
  4.     "fmt"
  5. )
  7. func mergeSort(nums []int) {
  8.     // 无需排序
  9.     if nums == nil || len(nums) < 2 {
  10.         return
  11.     }
  13.     ans := mergeSortHelp(nums)
  14.     copy(nums, ans)
  15. }
  17. func mergeSortHelp(nums []int) []int {
  18.     // 递归出口
  19.     if len(nums) < 2 {
  20.         return nums
  21.     }
  22.     // 分
  23.     mid := int(len(nums) / 2)
  24.     left := mergeSortHelp(nums[:mid])
  25.     right := mergeSortHelp(nums[mid:])
  26.     return merge(left, right) // 合
  27. }
  29. // 具体合并方法
  30. // 双指针合并两个有序数组
  31. func merge(left []int, right []int) []int {
  32.     temp := make([]int, len(left)+len(right))
  33.     i, j, k := 0, 0, 0
  34.     for i < len(left) && j < len(right) {
  35.         if left[i] < right[j] {
  36.             temp[k] = left[i]
  37.             i++
  38.         } else {
  39.             temp[k] = right[j]
  40.             j++
  41.         }
  42.         k++
  43.     }
  45.     for i < len(left) {
  46.         temp[k] = left[i]
  47.         i, k = i+1, k+1
  48.     }
  50.     for j < len(right) {
  51.         temp[k] = right[j]
  52.         j, k = j+1, k+1
  53.     }
  55.     return temp
  56. }
  58. func main() {
  59.     nums := []int{8, 2, 1, 9, 6, 4, 3, 7}
  60.     mergeSort(nums)
  61.     fmt.Println(nums)    
  62. }
  63. 输入如下：
  64. [1 2 3 4 6 7 8 9]

回顾整个过程，是不是会有这样的想法“为什么会想到这样拆分”，“原来还有这么巧妙的合并方法”等疑问。
没错，这就是递归的难点：“我怎么知道要这样拆分”，“我又怎么知道要这样合并”。

对于这两个难点，没有什么好的解决办法。

  1. 天资聪颖，一眼看出。（夸张了，是分析得出= =）
  2. 不断编程，积累经验。（慢慢成长）

最少有 K 个重复字符的最长子串

原题链接：最少有 K 个重复字符的最长子串
题目：

给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串， 要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度。 示例 1： 输入：s = “aaabb”, k = 3 输出：3 解释：最长子串为 “aaa” ，其中 ‘a’ 重复了 3 次。 示例 2： 输入：s = “ababbc”, k = 2 输出：5

解释：最长子串为 “ababb” ，其中 ‘a’ 重复了 2 次， ‘b’ 重复了 3 次。 提示：

1 <= s.length <= 分治与递归 - 图2

s 仅由小写英文字母组成

1 <= k <= 分治与递归 - 图3

如果用分治思想来思考这一题，第一步就是要思考如何划分？俗话说万事开头难，会划分，就基本解决了一半。

思考过程：
本题中，最长子串（记为 target ）要求该子串中的每一字符出现次数都不少于 k ，那么也就是说，如果一个子串包含了出现次数少于 k 的字符，那么它必然不符合要求，因此可以考虑以此作为划分依据。
先统计 s 中每个字符 c 的出现次数 times

  1. 若对于每一个 c 都有 times >= k，则 s 即为所求。
  2. 若存在一个 c 有 times <= k，说明 s 非所求，此时我们用这个 c 把 s 分割成若干子串，问题就转化为：在得到的每个子串中寻找 target，这是一个与原问题相同的子问题，但是规模变小了（字符串的长度变小了），因此可以使用递归解决。

现在问题来了，递归出口是什么呢？
换句话说，问题分解到哪个程度可以直接说出答案呢？
显然，当字符串长度小于 k 时，说明该字符串不可能是 target，结果为 0。

到此，“分”的过程基本结束，但是，
“治”的过程，还要解决：统计 s 中每个字符 c 的出现次数 times。
“合”的过程还要解决：每个子问题都可能有一个子问题的 target，如何合并成原问题的 target 呢？
这两个问题都比较简单，就不赘述了。

代码实现如下：

func longestSubstring(s string, k int) int {
    // 递归出口
    if len(s) < k {
        return 0
    }
    // 统计每个字符的出现次数
    counts := [26]int{}
    for i := range s {
        counts[s[i]-'a']++
    }
    // 尝试找到出现次数小于 k 的字符
    for i := range counts {
        if 0 < counts[i] && counts[i] < k {        // 找到了以它为分割符
            substrings := strings.Split(s, string('a'+byte(i)))        // 分
            ans := 0
            for j := range substrings {
                ans = max(ans, longestSubstring(substrings[j], k))    // 合
            }
            return ans
        }
    }

    return len(s)
}

func max(a, b int) int {
    if a < b {
        return b
    }
    return a
}