递归
关于递归是什么递归有什么用递归构成递归的使用条件
如何使用递归如何找递推关系?
递归时间复杂度分析
关于
递归是什么
简单说, 函数自己调用自己就叫递归
递归有什么用
简化代码: 只需少量代码就可描述出解题过程
简化问题: 把一个大型复杂问题转化为一个比原问题规模更小的子问题, 到子问题无需再次递归为止
递归构成
递归基例(递归出口)(bottom cases):最基本的情况, 递归到这种情况时, 不需要进一步的递归, 程序调用完成, 返回
递推关系(recurrentce relation):一个问题的结果与其子问题的结果之间的关系
递归的使用条件
1. 可以通过递归调用来缩小问题规模，且新问题与原问题有着相同的形式
2. 存在一种简单情境，可以使递归在简单情境下退出
下面举一个简单的例子来演示: 假如我们要计算m的n(n>0)次幂, 即mn
显然, 下面的式子成立 (递推关系):
m
n
=
m
×
m
×
m
×
.
.
.
×
m
m ^ n = m\times m\times m \times ...\times m
mn=m×m×m×...×m
m
×
m
n
−
1
=
m
×
m
×
m
×
.
.
.
×
m
m \times m ^ {n-1} =m\times m\times m\times ...\times m
m×mn−1=m×m×m×...×m 显然, 当n=1的时候 (递归出口)
m
1
=
m
m ^ 1=m
m1=m
/**
* 输入底数和指数计算幂
*
* @param m 底数
* @param n 指数
* @return m^n
*/
public static int pow(int m, int n) {
if (n == 1) // 递归出口
return m;
return m * pow(m, n - 1); // 递推关系
}
如何使用递归
写出递归最关键的就是找出递推关系和递归出口
递归出口往往是显而易见的, 就是那些最基本的情况, 比如n=0或n=1时的情况
比较复杂的是如何找出递推关系
如何找递推关系?
回顾上个计算幂的例子, 其中的递推关系是:
m
×
m
n
−
1
=
m
×
m
×
m
×
.
.
.
×
m
m \times m ^ {n-1} =m\times m\times m\times ...\times m
m×mn−1=m×m×m×...×m 所以,代码中:
m * pow(m, n - 1);
可见, 在写递归代码的时候, 我们不需要考虑 n-1或n+1需要做什么, 只需要指定当前的n需要做什么
下面举一个著名的递归例子: 汉诺塔(Hanoi),有A, B, C三根柱子和若干块大小不同的圆盘 现在, 把圆盘从下面开始按大小顺序重新摆放在另一根柱子上(从A移到C)。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘 这个问题该如何思考呢?
我们先想只有一个圆盘的情况(递归基例):
是不是直接把圆盘从A移到C就可以了😉
现在再想, A上有两个圆盘的情况:
1. 可以先把小的那个圆盘从A柱子移到B柱子上面: A->B
2. 再把较大的那个圆盘移到从A移到C上面: A->C
3. 然后把放在B上的那个圆盘放到C上: B->C
再想, A上有3个圆盘的情况(从上到下依次增大):
1. 把最上面的1移到C A->C
2. 把中间的2移到B A->B
3. 把C上的移到B C->B 此时我们已经把最后一个盘上面的所有盘移到了B
4. 把最下层的3移到C A->C
5. 把B上的1移到A B->A 相当于把两个盘从B移到C
6. 把B上的2移到C B->C
7. 把A上的1移到C A->C
我们观察上面两种情况, 不难发现步骤其实只有3步(假设有n个盘,从上到下编号1~n):
1. 把上面n-1个盘从A移到B
2. 把第n个盘从A移到C
3. 把n-1个盘从B移到C
也即
/**
* 汉诺塔
*
* @param a 起始柱
* @param b 辅助柱
* @param c 目标柱
* @param n 移动的次数
*/
public static void hannoi(char a, char b, char c, int n) {
if (n == 1) {// 只有一个盘的情况
System.out.println(a + " -> " + c);
return;
}
hannoi(a, c, b, n - 1);// 把前n-1个从a->b
System.out.println(a + " -> " + c);// 最后一个从a->c
hannoi(b, a, c, n - 1);// 最后把前n-1个从b-c
}
运行代码, 当n=10时, 需要移动 1023次
所以这种递归的问题, 在数据较大的时候, 用人脑去模拟势必会显得大脑不太够用
实际上在分析一个递归的问题时, 我们不需要跳进函数里面, 只需要指定这个函数的功能(如, 将圆盘从起始柱移到目标柱), 然后对当前的数据进行操作(如,System.out.println(a + " -> " + c); 第n个圆盘的起始柱和目标柱 )
应注意到, 递归调用函数的时候参数是在变化的: 起始柱, 目标柱, 辅助柱在变, 次数n也在变 找出递推关系的关键就是找到变化的量, 将它们作为参数传入函数
递归时间复杂度分析
就汉诺塔问题而言:
参数n代表问题的规模, 耗时用T(n)表示, 规模为n-1时的耗时为T(n-1) 当规模等于1时, 只需要移动一步即可, 耗时为O(1) 当规模大于1时, 先将n-1个圆盘从A移动到B, 耗时T(n-1) 将剩下的1个移动到C, 耗时O(1) 将B上的n-1个移动到C, 耗时T(n-1) 故:
T
(
n
)
=
{
O
(
1
)
,
n
=
1
2
T
(
n
−
1
)
+
O
(
1
)
,
n
>
1
T(n)=\begin{cases}O(1) ,n=1 \\2T(n-1)+O(1) ,n>1 \end{cases}
T(n)={O(1),n=12T(n−1)+O(1),n>1
当n>1时: 令c=O(1)
T
(
n
)
=
2
T
(
n
−
1
)
+
c
T(n)=2T(n-1)+c
T(n)=2T(n−1)+c
T
(
n
)
=
2
(
2
T
(
n
−
2
)
+
c
)
+
c
T(n)=2(2T(n-2)+c)+c
T(n)=2(2T(n−2)+c)+c
T
(
n
)
=
2
(
2
(
2
T
(
n
−
3
)
+
c
)
+
c
)
+
c
T(n)=2(2(2T(n-3)+c)+c)+c
T(n)=2(2(2T(n−3)+c)+c)+c
T
(
n
)
=
2
n
−
1
c
+
2
n
−
1
c
−
c
T(n)=2^{n-1}c+2^{n-1}c-c
T(n)=2n−1c+2n−1c−c
T
(
n
)
=
2
n
c
−
c
T(n)=2^nc-c
T(n)=2nc−c
O
(
n
)
=
2
n
O(n)=2^n
O(n)=2n
所以如果要计算移动的次数, n个圆盘就需要移动2n-1次