2015算法-第三章递归

递归的例子从前有座山，山上有座庙，庙里有个老和尚讲故事，讲的是从前有座山，山上有座庙，庙里有个老和尚讲故事，讲的是从前有座山，山上有座庙，庙里有个老和尚讲故事，讲的是……

……递归定义一个过程直接地或间接地调用自己，则称这个过程是递归的过程。递归算法在计算机理论和实际应用中都具有重要意义。设计和分析思路清晰，实现容易，但效率较低主要内容递归算法实现机制递归转非递归(略)递归算法设计递归关系式的计算(略)3.1

递归算法实现机制子程序实现原理子程序调用的一般形式值回传方式子程序调用的

操作递归程序实现原理5子程序调用的一般形式主程序Call

A1：子程序A主程序子程序ACall

A1：Call

A2：6(b)n次调用(a)1次调用一子程序调用的主程序Call

A1：子程序A子程序BCall

B2：子程序A主程序子程序BCall

A2：Call

B1：(c)嵌套调用(d)平行调用子程序调用时，用栈方式管理调用子程序时的返回地址7（包括局部变量）。值回传方式实参与形参的两种数据传送方式：值参与变参变参回传值，有两种方法：两次值传送方式按指定类型为变参设置相应的

空间。执行调用时，实参值传送给变参，返回时变参值传送给实参。地址传送方式在

将变参设置成一个地址，调用时将实参的地址传送给变参。本章

的递归问题对变参采用两次值传送方8式。procedure

f(integer

n)integer

y;if

(n0)then

return

1;else

y

nf

(n1);return

y;endifend

f递归求阶乘的算法procedure

g(n)：integer

fn;fn

f(4);return

fn;end

g9子程序调用的

操作执行调用时：返回地址进栈，开辟子程序的局部变量空间为子程序准备数据，即将实参值赋值给形参指令流转入子程序执行返回操作时：将变参或函数的值保存到回传变量中从栈顶取出返回地址按地址返回将回传变量中的值传送给相应的变量或位置上1011递归程序实现原理原理：一个递归过程的执行类似于多个子程序的嵌套调用。定义：递归过程直接地或间接地调用自己本身代码。特征：有递归调用、有递归出口。特点：设计和分析思路清晰，实现容易，效率较低。为了保证递归调用的正确性，需要保存调用点的现场（返回地址、局部变量、被调用函数的参数等），以便正确地返回，并且按先进后出的原则来管理这些信息。高级语言编译程序是利用栈来实现的。f(n)

f(n1)

f(n2)

f(1)

f(0)…调用返回调用点PnPn-1Pn-2P11调用时执行入栈操作保存现场，返回时执行出栈操作恢复现场.12procedure

f(integer

n)integer

y;if

(n0)

then

return

1endify

n

f(n1);return

y;end

f递归求阶乘的算法主程序：integer

fn;fn

f(4);13计算4!递归过程图示：下图中Pi

代表现场信息，栈元素由现场信息和参数构成f(4)4f(3)Push(e4)f(3)3f(2)Push(e3)f(2)2f(1)Push(e2)f(4)4f(3)f(3)

3f(2)f(2)

2f(1)

24

6f(1)

1f(0)

12P4

4P3

3P4

4P11Pop(P22P33P44f(1)1f(0)

f(0)1Push(e1)e1)Pop(P2

2P3

3P4

4e2)Pop(e3)Pop(e4)14153.3

递归算法设计递归设计需满足的要求递归求解的通用表现形式递归的几个典型例子16递归设计需满足的要求可以用递归求解的问题应满足：问题P的描述涉及规模，即P(size)；规模发生变化后，问题的性质不变；问题的解决有出口。递归求解的通用表现形式Procedure

P(参数表)if

递归出口简单操作thenelse简单操作call

P简单操作endifend

P规模或与规模相关的参数降低规模的处理对递归结果的处理1718几个典型例子简单的0/1背包问题n阶Hanoi塔问题棋子移动问题n个元素的全排列自然数拆分（正整数拆分）19例3.3

简单的0/1背包问题背包可容纳物品的最大质量为m，现有n件物品，质量分别为m1,m2,,mn，mi均为正整数，要从n件物品中挑选若干件，使放入背包的质量之和正好为m.简单的0/1背包问题例：m20,

n5,(m1,

m2,

m3,

m4,

m5)(3,5,8,9,10)(x1,x2,x3,x4,x5)(1,0,1,1,0)m18?

m28?注：对于第i件物品要么取，要么舍，不能取一部分，因此这个问题可能有解，也可能无解。布尔函数20问题分析knap(m,n)m初始：……m1

m2

….

…mn1mnm…….m1

m2

……mn1nm

mtruemnmmn1,即还有可选物品…….m1

m2

……knap(mmn,

n1)mn1有解

knap(m,n)

true无解

knap(m,n)

knap(m,n1)mn

mm…….m1

m2

……mn1knap(m,n1)n1否则

false21function

knap(m,

n)case:mmn0:

knap

true:mmn0:

if

n1

thenif

knap(mmn,n1)

true

thenknap

trueelse knap

knap(m,n1)endifelse

knap

false

endif:mmn0:

if

n1

then

knap

knap(m,n1)else

knap

false

;

endifendcase22例3.4

一个

的古老

_

汉诺塔在贝拿勒斯（在三根宝石针。北部）的圣庙里，一块黄铜板上插着教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔(Tower

of

Hanoi）。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。假如每秒钟一次，移完这些金片需要5845亿年以上。n阶Hanoi塔问题有n个圆盘依半径从小到大自上而下地套在柱子A上，柱子B和C没有圆盘。要求将A上的盘子换到C上，每次只移动一个，且不允许将大圆盘压在小圆盘的上面。24寻找递归出口XYZHanoi(n,X,Y,Z)圆盘数量源柱

辅助

目标柱

柱25n1,

X1Zn2,

X1YX2ZY1Zn阶Hanoi问题Hanoi(n,X,Y,Z)n3,Hanoi(2,X,Z,Y)X3ZHanoi(2,Y,X,Z)X26YZ27CABCABABC(1)Hanoi(n1,X,Z,Y)(2)

Xn

Z(3)

Hanoi(n1,Y,X,Z)XYZ圆盘

源柱

辅助

目标数量

柱

柱Hanoi(n,X,Y,Z)28n阶Hanoi问题procedure

Hanoi(n,

X,

Y,

Z)if

(n1)

then

move(X,

Z)elseHanoi(n1,

X,

Z,

Y)move(X,

Z)Hanoi(n1,

Y,

X,

Z)endifEnd

Hanoi例3.5

棋子移动问题有2n个棋子(n4)排成一行，白子用0表示，黑子用1表示，例如n5时初始状态为0

0

0

00

1

1

1

1

1

_

_（右边至少有两个空位），要求通过棋子移动最终成为0

1

0

1

0

1

0

1

0

1.29棋子移动问题移动规则每次必须同时移动相邻两个棋子颜色不限，移动方向不限每次移动必须跳过若干棋子不能调换这两个棋子的位置30寻找递归出口n400001111_

_step1000_

_11101(4,5)

(9,10)step20001011_

_1(8,9)

(4,5)step30_

_1011001(2,3)

(8,9)step4010101_

_01(7,8)

(2,3)step5_

_01010101(1,2)

(7,8)31n50000011111_

_step10000_

_111101(5,6)

(11,12)step200001111_

_01(9,10)

(5,6)32n6step1step2000000111111_

_00000_

_1111101 (6,7)

(13,14)0000011111__01

(11,12)

(6,7)chess(n)递归出口：n4;递归过程：n4时；move (n,n1)

(2n1,2n2)；move

(2n1,2n)

(n,n1);call

chess(n1);A(9)A(4)A(10)A(5)棋子的移动问题Procedure

Chess(n)if

n4

thenmove (4,5)

(9,10)move (8,9)

(4,5)move (2,3)

(8,9)move (7,8)

(2,3)move (1,2)

(7,8)elsemove (n,

n+1)

(2n+1,

2n+2)move (2n1,

2n)

(n,

n+1)call

Chess(n1)endif33递归出口递归调用End

Chess例3.6

求n个元素的全排列设A={a1,a2,…,an}是要进行排列的n个元素的集合，n1n2输出a1输出a1a2a2a1输出a1a2a3a1a3a2a2a1a3a2a3a1a3a2a1a3a1a2n3分析n3，排列按如下步骤进行：a1之后跟a2,a3的所有全排列；在上述全排列里，a1和a2位置互换；(3)在上述全排列里，a1和a3位置互换。34求n个元素的全排列range(A)

a1range(A1),

a2range(A2),,

anrange(An)集合A用数组实现range(A,1,n)：递归出口：range(A,n,n)递归调用：使得集合所有元素都可以作为前缀出现Aa1Aa2Aan35求n个元素的全排列if

kn

then

print(A)elseA(k)

A(i)repeatendifprocedure

range(A,k,n)

递归出口，打印整个数组A。for

i

k

to

n

do

A(i)与A(k)值互换A(k)

A(i)call

range(A,k1,n)缺省时，认为形参是in型，其值变化时不回传end

range36ocall

range(A,1,n)range(A,1,3)If

13

then

print(A)elsefor

i

1

to

3

doA(1)A(i);call

range(A,2,3)

略abcA={a,

b,

c}1)

i1,

aa

A{a,b,c}2)

i2,

bb

A{a,b,c}acb3)

i3,

bc

A{a,c,b}bac4)

i2,

a

b

A{b,a,c}5)

i2,

aa

A{b,a,c}bca6)

i3,

ac

A{b,c,a}range(A,2,3)…for

i2

to

3doA(2)A(i);call

range(A,3,3)

略range(A,3,3)if

33

print(A)略7)

i3,

ac

A{c,b,a}cba8)

i2,

bb

A{c,b,a}cab9)

i3,

ba

A{c,a,b}例3.7

自然数拆分任何一个大于1的自然数n，总可以拆分成若干个小于n的自然数之和，试求n的所有拆分。n2n3211312111413112111122n438自然数拆分（正整数拆分）n66

15114

113

1112111111112212324222333940自然数拆分（正整数拆分）拆分的结果用一维数组A保存；对任意自然数的所有拆分方式，依据A(1)的值，可以分为n/2类；第i类第一行元素是A[1]i，A[2]ni；为保证拆分不重复，A中元素是非降的；下一次的拆分，用A的下标来控制，而不是A中的元素值；发生下一次拆分（递归调用）的判断条件。自然数拆分（正整数拆分）算法procedure

split(t)j

t;

L

A(j)end

splitprocedure

main(n)end

main41输出已产生的一种拆分本次拆分的起始位置本次拆分的数值split(2)Print:1,3j2;

L3i在1~3/2之间

i1:

A[2]1;A[3]

2;main(4)i在1~4/2之间

i1:

A[1]1;A[2]3;i2:

A[1]2;A[2]2;1split(3)Print:1,1,2j3;

L2i在1~2/2之间

i1:

A[3]

1;A[4]

12split(4)Print:1,1,1,1j4;

L1i在1~1/2之间3split(2)Print:2,2j2;

L3i在2~2/2之间442433.4

递归关系式的计算递归算法的时间复杂度分析K阶线性齐次递归关系式的解法求n个元素的最大元问题Procedure MAX

(A,i,

j)if

ij

then

return

A(i)

endifif

ji1

thenif

A(i)A(j)

then

return

A(i)else

return

A(j)

;

endifelsek

(ij)/2m1

MAX(i,

k)m2

MAX(k1,

j)if

m1m2

then

return

m1else

return

m2;

endifendifend

MAX44递归算法的时间复杂度分析求n个元素的最大元问题二分法Max(A,1,n)A(1)A(2)

A(n/2)

A(n/21)

A(n)Max(A,1,

n/2)Max(A,n/21,n)max45时间复杂性46n

2

2

C

n

2T

C1T

n

n

2247台阶问题一个楼有n个台阶，有一个人上楼时有时一次跨一个台阶，有时跨两个台阶，写算法，计算此人有几种不同的上楼方法，并分析算法的时间复杂度。48台阶问题procedure

H(n)if

n2

then

HnelseHH(n1)H(n2)endifend

H49时间复杂性

n

2T n

1

T

n

2

n

2T

(n)

2T

(n

1)

22

T

(n

2)

...

2n1T

(1)

(2n

)T

n

C所以，50k阶线性齐次递归关系式的解法定义3.1

递归关系式其中，ck0，ci1，bi是给定常数，称为k阶线性常系数递归关系式。当d(n)0时，称此