数学归纳法之递归求值
1. 数学归纳法
数学归纳法是证明当 n 等于任意一个自然数时某命题成立。证明分为起始步骤（basics）和递推步骤（induction step）两步：
-
证明当 n = 1 时，命题成立。
-
证明如果 n = m 时命题成立，那么可以推导出在 n = m + 1 时命题成立。
2. 阶乘
阶乘的定义公式：
n! = 1 × 2 × ... × (n-2) × (n - 1) × n
阶乘的递推公式：
n! = n × (n-1)!
我们可以用数学归纳法证明阶乘的递推公式如下：
-
根据阶乘的定义，当 n = 0 或 n = 1 时，0! = 1 或 1! = 1，命题成立。
-
假设 n = m 时，m! = m × (m - 1)!， 当 n = m + 1 时，则 (m + 1)! = (m + 1) × [(m + 1) - 1]! = (m + 1) × m!，命题成立。
3. 函数和递归
如果我们把 n 的阶乘函数（function）定义为 f(n) = n! ，当 n = 0 或 1时，n! = 1 ，则根据阶乘的递推公式，我们有 f(n) = n × (n - 1)! = n × f(n - 1) 。也就是说，我们要求值 f(n) ，就要求值 f(n - 1) ，再求值 f(n - 2) … f(2) , 最后求值 f(1) ，而这个函数 f 调用自己 f 的情况，我称之为递归（recursion）。
4. 递归求解
递归的用途是用于将一个大的问题，重复分解为相同或相似的子问题，直到子问题小到可以直接求解。
当子问题需要继续分解时，我们称这种情况为递归情况（recursive case）。
当子问题可以直接解决时，递归终止并回升，我称这种情况为基本情况（base case）。
以阶乘函数为例，f(0) = 1 和 f(1) = 1 为基本情况，f(n) = n × f(n - 1)，n > 1 属于递归情况。
// Go 语言，递归求解阶乘
package main
import (
"fmt"
)
func main() {
n := 5
f := factorial(n)
fmt.Printf("%d! = %d\n", n, f)
// Output:
// n = 5: 5 * factorial(4)
// n = 4: 4 * factorial(3)
// n = 3: 3 * factorial(2)
// n = 2: 2 * factorial(1)
// n = 1: 1
// 5! = 120
}
func factorial(n int) int {
if n == 0 || n == 1 { // base case
fmt.Printf("n = %d: %d\n", n, 1)
return 1
}
fmt.Printf("n = %d: %d * factorial(%d)\n", n, n, n-1)
return n * factorial(n-1) // recursive case
}5. 尾调用和尾递归
在计算机科学中，尾调用（tail call）是指一个函数的最后一个动作是返回一个函数的调用结果的情形，即最后一步新调用的函数返回值被当成当前函数的返回结果。如果递归函数（recursion）满足尾调用的定义，则称这种递归为尾递归（tail recursion）。
// Go 语言，尾递归求解阶乘
package main
import (
"fmt"
)
func main() {
n := 5
f := tail_recursive_factorial(n, 1)
fmt.Printf("%d! = %d\n", n, f)
// Output:
// n = 5: tail_recursive_factorial(4, 5*1)
// n = 4: tail_recursive_factorial(3, 4*5)
// n = 3: tail_recursive_factorial(2, 3*20)
// n = 2: tail_recursive_factorial(1, 2*60)
// n = 1: 120
// 5! = 120
}
func tail_recursive_factorial(n, f int) int {
if n == 0 || n == 1 { // base case
fmt.Printf("n = %d: %d\n", n, f)
return f
}
fmt.Printf("n = %d: tail_recursive_factorial(%d, %d*%d)\n", n, n-1, n, f)
return tail_recursive_factorial(n-1, n*f) // recursive case
}6. 分治法
在计算机科学中，分治法（divide and conquer）是基于多分支递归的一个算法设计模式。分治算法是将问题递归的分解成两个或多个相同或相关类型的子问题，直到这些子问题简单到可以直接求解。最后将子问题的解进行合并得到原始问题的解。分治法是许多高效算法的技术基础，如排序中的归并排序（merge sort）和快速排序（quick sort）等等。
分治法的求解步骤如下：
-
分解:原问题为若干子问题，这些子问题是原有问题的规模较小的实例
-
解决:这些子问题，递归地求解各子问题。若子问题的规模足够小，则直接求解
-
合并:这些子问题的解成原问题的解
快速排序算法：
-
分解: 选择主元 P(viot), 将待排序序列分割成两个区域（partitions），左边的分区的元素都小于或等于 P，右边的元素大于 P
-
解决: 对左右两个分区进行递归的快速排序
-
合并: 由于序列是原址排序，分区的操作即为排序的操作，无需合并
// Go 语言，快速排序
package main
import (
"fmt"
)
func main() {
s := []int{8, 5, 2, 6, 9, 3, 1, 4, 0, 7}
fmt.Println("Before:", s)
quick_sort(s, 0, len(s))
fmt.Println("After:", s)
// Output:
// Before: [8 5 2 6 9 3 1 4 0 7]
// low: 0, high: 10, pivot: 7, s: [5 2 6 3 1 4 0 7 9 8]
// low: 0, high: 07, pivot: 0, s: [0 2 6 3 1 4 5 7 9 8]
// low: 0, high: 07, pivot: 5, s: [0 2 3 1 4 5 6 7 9 8]
// low: 0, high: 05, pivot: 4, s: [0 2 3 1 4 5 6 7 9 8]
// low: 0, high: 04, pivot: 1, s: [0 1 3 2 4 5 6 7 9 8]
// low: 1, high: 04, pivot: 2, s: [0 1 2 3 4 5 6 7 9 8]
// low: 2, high: 04, pivot: 3, s: [0 1 2 3 4 5 6 7 9 8]
// low: 5, high: 07, pivot: 6, s: [0 1 2 3 4 5 6 7 9 8]
// low: 7, high: 10, pivot: 8, s: [0 1 2 3 4 5 6 7 8 9]
// low: 8, high: 10, pivot: 9, s: [0 1 2 3 4 5 6 7 8 9]
// After: [0 1 2 3 4 5 6 7 8 9]
}
func quick_sort(s []int, low, high int) {
if high-low > 1 { // recursive case
mid := partition(s, low, high)
quick_sort(s, low, mid)
quick_sort(s, mid, high)
}
// base case
}
func partition(s []int, low, high int) int {
pivot := s[high-1]
i := low - 1
for j := low; j < high-1; j++ {
if s[j] <= pivot { // compare
i++
s[j], s[i] = s[i], s[j] // swap
}
}
s[i+1], s[high-1] = s[high-1], s[i+1]
fmt.Printf("low: %d, high: %02d, pivot: %d, s: %v\n", low, high, pivot, s)
return i + 1
}7. 动态规划
动态规划（英语：Dynamic programming，简称DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。
动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。
通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。
以求斐波那契数列为例：
// a naive algorithm with time O(2^n) and space O(n)
func fib(n int) int {
// base case
if n <= 1 {
return n
}
// recursive case
return fib(n-1) + fib(n-2)
}// a dynamic programming algorithm with time O(n) and space O(n)
func fib(n int) int {
if n <= 1 {
return n
}
f := make([]int, n+1)
f[0] = 0
f[1] = 1
for i := 2; i <= n; i++ {
f[i] = f[i-1] + f[i-2]
}
return f[n]
}8. 调用栈和调用帧
在计算机科学中，调用栈（call stack）是一种存储函数调用上下文的数据结构，比如局部变量，函数返回控制点等等。
调用栈是由一系列的调用帧（stack frame）的栈结构形式组成。每次发起一个函数调用，都会对新的调用创建新的调用帧。
我们以当 n = 3 的阶乘为例，调用栈（bottom to up）如下所示：
n = 1, f = 1 ------------------ n = 2, f = 2 * f(1) ------------------ n = 3, f = 3 * f(2) ------------------
调用栈的大小通常是有限的，如果持续创建调用帧，则会导致调用栈溢出（stack overflow）。
比如对于递归调用，如果一直没有触发基本情况进行终止调用，进行递归回升，则会导致栈溢出。
// Go 语言，栈溢出
package main
func main() {
f()
// Output:
// runtime: goroutine stack exceeds 1000000000-byte limit
// fatal error: stack overflow
}
func f() {
f()
}9. 尾调用优化
我们知道尾递归是一种特性的尾调用，下面看下当 n = 3 的阶乘的尾递归调用栈：
n = 1, f = 6 ------------------ n = 2, f = f(1, 2 * 3) ------------------ n = 3, f = f(2, 3 * 1) ------------------
和上述的非尾递归的调用栈比较，我们会发现，尾递归的每次新的调用并不依赖下一个调用帧的返回结果，所以我们可以把这些调用帧减少至一个并重复使用，这种情况就叫做尾递归优化或者尾调用优化（tail call optimaization）。