第二章 递归与分治 2021/2/21 计算机算法设计与分析
2021/2/21 计算机算法设计与分析 1 第二章 递归与分治
递归的概念 ■简单地说,递归就是用自己来定义自己。 ■一般地说,一个递归过程P可以表示为基语句 S(不含P和P自身的组合β: P≡β(S,P) ■这样的表示包含了过程不终止的可能,因此递 归算法应更准确地表述为 P≡ if b then Q elseβ(S,P) 其中Q也不包含P,B为递归终止条件。 2021/22 计算机算法设计与分析 2
2021/2/21 计算机算法设计与分析 2 递归的概念 ◼ 简单地说，递归就是用自己来定义自己。 ◼ 一般地说，一个递归过程P可以表示为基语句 S(不含P)和P自身的组合β： P β(S, P) ◼ 这样的表示包含了过程不终止的可能，因此递 归算法应更准确地表述为 P if B then Q else β(S, P) 其中Q也不包含P，B为递归终止条件
递归元 ■递归算法的思想是将对较大规模的对象的操作 归结为对较小规模的对象实施同样的操作。 ■这种规模的变化就体现在递归算法的变元中的 类(一个或几个)变元上,这类变元被称之为 递归元。 递归元的变化是在递归定义中确定的,它的变 化应能导致递归算法的终止。 在递归算法的设计中递归元是非常重要的 2021/22 计算机算法设计与分析 3
2021/2/21 计算机算法设计与分析 3 递归元 ◼ 递归算法的思想是将对较大规模的对象的操作 归结为对较小规模的对象实施同样的操作。 ◼ 这种规模的变化就体现在递归算法的变元中的 一类(一个或几个)变元上，这类变元被称之为 递归元。 ◼ 递归元的变化是在递归定义中确定的，它的变 化应能导致递归算法的终止。 ◼ 在递归算法的设计中递归元是非常重要的
Hanoi塔问题 ■ Hanoi塔的解可以很自然地看成这样一个过程: (1)先将A上面于是可得到如下的程序 n-1个盘移至C。 void hanoi(int n, int Fr; int To, int as) (2)再将A上剩下 的1个盘移至B Hanoi(n-1, Fro, AsS, To Move(fro, To); (3)最后将C上的 Hanoi(n-1, ASS, To, Fro) n-1个盘移至B 2021/221 计算机算法设计与分析
2021/2/21 计算机算法设计与分析 4 Hanoi塔问题 ◼ 例1：Hanoi塔问题：有A、B、C三根柱子。A 上有n个圆盘，自下而上由大到小地叠在一起。 A B C ◼ 现要将A上的全部圆 盘移到B上，并要求： (1)每次只能移动一个 圆盘；(2)任何时刻都 不允许将较大的圆盘 压在较小的圆盘上； (3)圆盘只能在A、B、 C三个柱子间移动。 ◼ Hanoi塔的解可以很自然地看成这样一个过程： (1)先将A上面 n–1个盘移至C。 (2)再将A上剩下 的1个盘移至B。 (3)最后将C上的 n–1个盘移至B。 于是可得到如下的程序： void Hanoi(int n, int Fr, int To, int As) { if (n > 0) { Hanoi(n–1, Fro, Ass, To); Move(Fro, To); Hanoi(n–1, Ass, To, Fro)} }
Hanoi塔问题的时间复杂性 Hanoi塔问题的时间复杂性为O(2n) ■证明:对n归纳证明移动次数move(n)=2n-1。 ■归纳基础:当n=1,move(1)=1=21-1 ■归纳假设:当n≤k,move(n)=2n-1 ■归纳步骤:当n=k+1,移动次数为 move(k+1)=2move(k)+1=2(2k-1)+1 2 k+1 由归纳法可知对任意的n有move(n)=2n-1 2021/221 计算机算法设计与分析 5
2021/2/21 计算机算法设计与分析 5 Hanoi塔问题的时间复杂性 ◼ Hanoi塔问题的时间复杂性为O(2n )。 ◼ 证明：对n归纳证明移动次数move(n) = 2n – 1。 ◼ 归纳基础：当n = 1， move(1) = 1 = 2 1 – 1。 ◼ 归纳假设：当n k， move(n) = 2 n – 1。 ◼ 归纳步骤：当n= k + 1，移动次数为 ◼ move(k+1) = 2(move(k)) + 1 = 2(2k – 1) + 1 = 2k+1 – 1 ◼ 由归纳法可知对任意的n有move(n) = 2n – 1
常见的递归形式 除基本的递归形式外,其它常见的递归 形式有四种,它们是: ■多变元递归 ■多步递归; ■嵌套递归; ■联立递归 2021/221 计算机算法设计与分析 6
2021/2/21 计算机算法设计与分析 6 常见的递归形式 ◼ 多变元递归； ◼ 多步递归； ◼ 嵌套递归； ◼ 联立递归 • 除基本的递归形式外，其它常见的递归 形式有四种，它们是：
多变元递归 例2:整数划分问题:将一个正整数n表示为 一系列正整数之和, n=n1+n2+…+nk 其中n1>n2≥…n21,k>1。 例如p(6)=11,即整数6的划分数为11种 6.5+1.4+2.4+1+1.3+3.3+2+1.3+1+1+1 2+2+2.2+2+1+1.2+1+1+1+1,1+1+1+1+1+1 2021/221 计算机算法设计与分析
2021/2/21 计算机算法设计与分析 7 多变元递归 •◼例多变元递归就是递归元多于一个的递归。 2：整数划分问题：将一个正整数n表示为 一系列正整数之和， n = n1 + n2 +…+nk 其中n1≥n2≥…≥nk≥1, k≥1。 • 正整数n的一个这种表示称为正整数n的一个 划分。正整数n的不同的划分的个数成为正整 数n的划分数，记作ρ(n)。 • 例如ρ(6) = 11 ，即整数6的划分数为11种： 6, 5+1, 4+2, 4+1+1, 3+3, 3+2+1, 3+1+1+1 2+2+2, 2+2+1+1, 2+1+1+1+1， 1+1+1+1+1+1
正整数的划分 在正整数的所有不同划分中,将最大加数n不 大于m的划分个数记为q(n,m),可以建立如下 的二元递归函数: q(n, m)i if(n< 1)(m<1) return 0 if(n m return 1 if(n===1)(n< m) return 1+q(n, n-1) return q(n, m-1)+q(n-m, m);) 整数n的划分数p(n)=q(n,n)。 2021/22 计算机算法设计与分析
2021/2/21 计算机算法设计与分析 8 正整数的划分 ◼ 在正整数的所有不同划分中，将最大加数n1不 大于m的划分个数记为q(n, m)，可以建立如下 的递归关系： ◼ 最简单情形：(1) q(n, 1)=1, q(1, m) =1 n, m≥1; ◼ 递归关系： (2) q(n, n) = 1 + q(n, n–1)，n＞1; ◼ 产生的新情况： ◼ (3) q(n, m) = q(n, m–1) + q(n–m, m), n＞m＞1 ◼ (4) q(n, m) = q(n, n), n＜m。 1 n = 1 或 m = 1 q(n, m) = 1 + q(n, n–1) n ≤ m q(n, m–1)+q(n–m, m) n＞m＞1 的二元递归函数： q(n, m) { if (n < 1) || (m < 1) return 0; if (n == 1) || (m == 1) return 1; if (n == 1) || (n < m) return 1 + q(n, n–1); return q(n, m–1) + q(n–m, m); } ◼ 整数n的划分数ρ(n) = q(n, n)
多步递归 若递归函数f(x,y),其中y是递归元,不仅与f(x, y-1)有关,而且与fx,y-2),……,乃至(x,0) 有关,则称为多步递归。 ■例如 Fibonacci数 n=0 F(n)=1 F(n-1)+F(n-2)n>1 Fibonacci函数是一个两步的递归函数 2021/221 计算机算法设计与分析 9
2021/2/21 计算机算法设计与分析 9 多步递归 ◼ 若递归函数f(x, y)，其中y是递归元，不仅与f(x, y–1)有关，而且与f(x, y–2)，……，乃至f(x, 0) 有关，则称为多步递归。 ◼ 例如Fibonacci函数： 1 n = 0 F(n) = 1 n = 1 F(n–1) + F(n–2) n > 1 ◼ Fibonacci函数是一个两步的递归函数
嵌套递归 ■所谓嵌套递归是指递归调用中又含有递归调用, 又称为多重递归 例如 Ackermann函数: +1 X=0 A(x,y)=A(x-1,1) 0 A(x-1,A(x,y-1)x,y>0 Ackermann函数是一个双重的递归函数。同时 它也是个二元递归。 2021/221 计算机算法设计与分析 10
2021/2/21 计算机算法设计与分析 10 嵌套递归 ◼ 所谓嵌套递归是指递归调用中又含有递归调用， 又称为多重递归。 ◼ 例如Ackermann函数： y + 1 x = 0 A(x, y) = A(x–1, 1) y = 0 A(x–1, A(x, y–1)) x, y > 0 ◼ Ackermann函数是一个双重的递归函数。同时 它也是个二元递归