分治法和递归

在计算机科学中，分治法是一种很重要的算法。

字面上的解释是分而治之，就是把一个复杂的问题分成两个或更多的相同或相似的子问题。

直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

分治法一般使用递归来求问题的解。

一、递归

递归就是不断地调用函数本身。

比如我们求阶乘 1 * 2 * 3 * 4 * 5 *...* N：

  1. package main
  2. import "fmt"
  4. func Rescuvie(n int) int {
  5.     if n == 0 {
  6.         return 1
  7.     }
  9.     return n * Rescuvie(n-1)
  10. }
  12. func main() {
  13.     fmt.Println(Rescuvie(5))
  14. }

会反复进入一个函数，它的过程如下:

  1. Rescuvie(5)
  2. {5 * Rescuvie(4)}
  3. {5 * {4 * Rescuvie(3)}}
  4. {5 * {4 * {3 * Rescuvie(2)}}}
  5. {5 * {4 * {3 * {2 * Rescuvie(1)}}}}
  6. {5 * {4 * {3 * {2 * 1}}}}
  7. {5 * {4 * {3 * 2}}}
  8. {5 * {4 * 6}}
  9. {5 * 24}
  10. 120

函数不断地调用本身，并且还乘以一个变量：n * Rescuvie(n-1)，这是一个递归的过程。

很容易看出, 因为递归式使用了运算符，每次重复的调用都使得运算的链条不断加长，系统不得不使用栈进行数据保存和恢复。

如果每次递归都要对越来越长的链进行运算，那速度极慢，并且可能栈溢出，导致程序奔溃。

所以有另外一种写法，叫尾递归：

  1. package main
  2. import "fmt"
  4. func RescuvieTail(n int, a int) int {
  5.     if n == 1 {
  6.         return a
  7.     }
  9.     return RescuvieTail(n-1, a*n)
  10. }
  13. func main() {
  14.     fmt.Println(RescuvieTail(5, 1))
  15. }

他的递归过程如下:

  1. RescuvieTail(5, 1)
  2. RescuvieTail(4, 1*5)=RescuvieTail(4, 5)
  3. RescuvieTail(3, 5*4)=RescuvieTail(3, 20)
  4. RescuvieTail(2, 20*3)=RescuvieTail(2, 60)
  5. RescuvieTail(1, 60*2)=RescuvieTail(1, 120)
  6. 120

尾部递归是指递归函数在调用自身后直接传回其值，而不对其再加运算，效率将会极大的提高。

如果一个函数中所有递归形式的调用都出现在函数的末尾，我们称这个递归函数是尾递归的。当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时，这个递归调用就是尾递归。尾递归函数的特点是在回归过程中不用做任何操作，这个特性很重要，因为大多数现代的编译器会利用这种特点自动生成优化的代码。— 来自百度百科。

尾递归函数，部分高级语言编译器会进行优化，减少不必要的堆栈生成，使得程序栈维持固定的层数，不会出现栈溢出的情况。

我们将会举多个例子说明。

二、例子：斐波那契数列

斐波那契数列是指，后一个数是前两个数的和的一种数列。如下：

  1. 1 1 2 3 5 8 13 21 ... N-1 N 2N-1

尾递归的求解为：

  1. package main
  2. import "fmt"
  5. func F(n int, a1, a2 int) int {
  6.     if n == 0 {
  7.         return a1
  8.     }
  10.     return F(n-1, a2, a1+a2)
  12. }
  14. func main() {
  15.     fmt.Println(F(1, 1, 1))
  16.     fmt.Println(F(2, 1, 1))
  17.     fmt.Println(F(3, 1, 1))
  18.     fmt.Println(F(4, 1, 1))
  19.     fmt.Println(F(5, 1, 1))
  20. }

输出：

  1. 1
  2. 2
  3. 3
  4. 5
  5. 8

当 n=5 的递归过程如下:

  1. F(5,1,1)
  2. F(4,1,1+1)=F(4,1,2)
  3. F(3,2,1+2)=F(3,2,3)
  4. F(2,3,2+3)=F(2,3,5)
  5. F(1,5,3+5)=F(1,5,8)
  6. F(0,8,5+8)=F(0,8,13)
  7. 8

三、例子：二分查找

在一个已经排好序的数列，找出某个数，如：

  1. 1 5 9 15 81 89 123 189 333

从上面排好序的数列中找出数字 189。

二分查找的思路是，先拿排好序数列的中位数与目标数字 189 对比，如果刚好匹配目标，结束。

如果中位数比目标数字大，因为已经排好序，所以中位数右边的数字绝对都比目标数字大，那么从中位数的左边找。

如果中位数比目标数字小，因为已经排好序，所以中位数左边的数字绝对都比目标数字小，那么从中位数的右边找。

这种分而治之，一分为二的查找叫做二分查找算法。

递归解法：

  1. package main
  3. import "fmt"
  5. // 二分查找递归解法
  6. func BinarySearch(array []int, target int, l, r int) int {
  7.     if l > r {
  8.         // 出界了，找不到
  9.         return -1
  10.     }
  12.     // 从中间开始找
  13.     mid := (l + r) / 2
  14.     middleNum := array[mid]
  16.     if middleNum == target {
  17.         return mid // 找到了
  18.     } else if middleNum > target {
  19.         // 中间的数比目标还大，从左边找
  20.         return BinarySearch(array, target, 0, mid-1)
  21.     } else {
  22.         // 中间的数比目标还小，从右边找
  23.         return BinarySearch(array, target, mid+1, r)
  24.     }
  26. }
  28. func main() {
  29.     array := []int{1, 5, 9, 15, 81, 89, 123, 189, 333}
  30.     target := 500
  31.     result := BinarySearch(array, target, 0, len(array)-1)
  32.     fmt.Println(target, result)
  34.     target = 189
  35.     result = BinarySearch(array, target, 0, len(array)-1)
  36.     fmt.Println(target, result)
  37. }

输出：

  1. 500 -1
  2. 189 7

可以看到，189 这个数字在数列的下标 7 处，而 500 这个数找不到。

当然，递归解法都可以转化为非递归，如：

  1. package main
  3. import "fmt"
  5. // 二分查找非递归解法
  6. func BinarySearch2(array []int, target int, l, r int) int {
  7.     ltemp := l
  8.     rtemp := r
  10.     for {
  11.         if ltemp > rtemp {
  12.             // 出界了，找不到
  13.             return -1
  14.         }
  16.         // 从中间开始找
  17.         mid := (ltemp + rtemp) / 2
  18.         middleNum := array[mid]
  20.         if middleNum == target {
  21.             return mid // 找到了
  22.         } else if middleNum > target {
  23.             // 中间的数比目标还大，从左边找
  24.             rtemp = mid - 1
  25.         } else {
  26.             // 中间的数比目标还小，从右边找
  27.             ltemp = mid + 1
  28.         }
  29.     }
  30. }
  32. func main() {
  33.     array := []int{1, 5, 9, 15, 81, 89, 123, 189, 333}
  34.     target := 500
  35.     result := BinarySearch2(array, target, 0, len(array)-1)
  36.     fmt.Println(target, result)
  38.     target = 189
  39.     result = BinarySearch2(array, target, 0, len(array)-1)
  40.     fmt.Println(target, result)
  41. }

很多计算机问题都可以用递归来简化求解，理论上，所有的递归方式都可以转化为非递归的方式，只不过使用递归，代码的可读性更高。