[算法设计与分析-从入门到入土] 递归

[算法设计与分析-从入门到入土] 递归

知乎：https://www.zhihu.com/people/byzh_rc

CSDN：https://blog.csdn.net/qq_54636039

注：本文仅对所述内容做了框架性引导，具体细节可查询其余相关资料or源码

参考文章：各方资料

递归recursion

递归技术存在三种特殊情况：

1. 归纳法Induction：数学证明中的归纳思想
2. 非重叠子问题Nonoverlapping：分治法(拆成p个子问题)
3. 重叠子问题overlapping：动态规划(自底向上)(以空间换取时间)

1.归纳法Induction

核心思想:
对于参数为n的问题, 先假设 “参数小于n的子问题已解决”（归纳假设）, 再将子问题扩展到参数为n的情况

以选择排序求解数组A[1...n]为例

归纳假设：假设长度为n-1的子数组A[1...n-1]已能成功排序

原问题转化：要解决长度为n的原数组排序，只需先在整个数组A[1...n]中找到最小值min，将其与数组第一个元素交换位置；此时原数组被拆分为“已确定有序的最小值min”和“待排序的子数组A[1...n-1]”
[ m i n , A [ 1... n − 1 ] ] \big[ min, A[1...n-1] \big][min,A[1...n−1]]
通过这一过程，原问题的规模从n缩小到n-1，最终可递推至规模为1（单个元素天然有序）的基准情况，完成整个排序

通过递推式计算比较次数：
C o m p a r e ( n ) = { 0 n = 1 ( n − 1 ) + C ( n − 1 ) n ≥ 2 = n ( n − 1 ) 2 \begin{align} Compare(n) &= \begin{cases} 0 & n=1 \\ (n-1) + C(n-1) & n \geq 2 \end{cases} \\ &= \frac{n(n-1)}{2} \end{align}Compare(n)​={0(n−1)+C(n−1)​n=1n≥2​=2n(n−1)​​​

全排列生成generating permutation

目的: 给定整数n nn，生成由数字1 , 2 , … , n 1,2,\dots,n1,2,…,n构成的所有排列

归纳假设：已能生成n − 1 n-1n−1个元素的所有排列

原问题转化: 将第n nn个元素插入到所有可能位置，从而生成n nn个元素的排列

1. 固定数字 1 在首位，递归生成{ 2 , 3 , … , n } \{2,3,\dots,n\}{2,3,…,n}的所有排列；
2. 固定数字 2 在首位，递归生成{ 1 , 3 , … , n } \{1,3,\dots,n\}{1,3,…,n}的所有排列；
3. 依次类推，直到固定数字n nn在首位

时间复杂度:Θ ( n ∗ n ! ) \Theta(n*n!)Θ(n∗n!)
空间复杂度:Θ ( n ) \Theta(n)Θ(n)

递推式写成:
f ( n ) = { 0 n = 1 n f ( n − 1 ) + n n ≥ 2 f(n)= \begin{cases} 0 &n=1 \\ nf(n-1)+n & n \geq2 \end{cases}f(n)={0nf(n−1)+n​n=1n≥2​

令f ( n ) = n ! h ( n ) f(n)=n!h(n)f(n)=n!h(n),

则n ! h ( n ) = n ( n − 1 ) ! h ( n − 1 ) + n n!h(n)=n(n-1)!h(n-1)+nn!h(n)=n(n−1)!h(n−1)+n
则h ( n ) = h ( n − 1 ) + 1 ( n − 1 ) ! < e − 1 h(n)=h(n-1)+\frac{1}{(n-1)!}<e-1h(n)=h(n−1)+(n−1)!1​<e−1

->f ( n ) < n ! ( e − 1 ) f(n)<n!(e-1)f(n)<n!(e−1)

e.g. 对于集合{1, 2, 3, 4}:

1234,2134,3124,4123,

(1234), 1324, 1423,
(2134), 2314, 2413,
(3124), 3214, 3412,
(4123), 4213, 4312,

(1234), 1243
(2134), 2143
(3124), 3142
(4123), 4132
(1324), 1342,
(1423), 1432,
(2314), 2341,
(2413), 2431,
(3214), 3241,
(3412), 3421,
(4213), 4231,
(4312), 4321

->A 4 4 = 24 A_4^4=24A44​=24

2.分治法divide and conquer

• 找到多数元素
• 最小 / 最大值查找
• 第 k 小元素查找

3.动态规划dynamic programming

• 最长公共子序列问题LCS
• 全对最短路径问题(All-Pairs Shortest Path)
• 0/1背包问题Knapsack