递归与回溯算法.ppt

1递归与回溯算法 2 递归的定义: 在定义一个过程或函数时出现调用本过程或本函数的成分,称为递归。若调用自身,称为直接递归。若过程或函数 p调用过程或函数 q,而 q又调用 p,则称为间接递归。在程序设计中,使用递归技术往往使函数的定义和算法的描述简洁且易于理解。递归的使用: 0 )!1(* 01!???????nnn nn Function jiech(n:integer):longint ; Begin if n=0 then jiech :=1 else jiech :=n * jiech(n-1); End; 3 ????????????1)2()1( 1 1 0 1)(nnfnf n n nf Function fib(n:integer):longint ; Begin if(n =0)or(n=1)then fib:=1 else fib:=fib(n-1)+fib(n-2); End; 爬楼梯时可以 1次走 1个台阶,也可以 1次走 2个台阶。对于由 n个台阶组成的楼梯,共有多少种不同的走法? 1个台阶:只有 1种走法; 2个台阶:有两种走法; (1+1 ; 2) N个台阶(n>2) ,记走法为 f(n ): 第1次走 1个台阶,还剩(n-1) 个台阶,走法为 f(n-1) ; 第1次走 2个台阶,还剩(n-2) 个台阶,走法为 f(n-2) 。所以, f(n )=f(n-1)+f(n-2) 。定义 f(0)=1 ,则有: 4 ,采用递归的方法编写算法既方便又有效。如单链表: Type node=^ lnode lnode =record data:integer ; next:node ; end; 求一个不带头结点的单链表 head 的所有 data 域之和的递归算法如下: Function sum(head:node):integer ; Begin if head=nil then sum:=0 else sum:= head^.data+sum( ); End; 5 :整数划分问题(版本 1) 为避免重复,记 nnn nnn k kn ???????????????? 21 211 其中 , 设 f(n,k )为把正整数 n分成 k份的分法,那么: 先考虑特殊情况: ⑴ f(n,1)=1 (n=n) ⑵ f(n,n )=1 (n=1+1+ ……+1) ⑶当 k>n 时, f(n,k )=0 (4) 若 n1=1 ,则: 其分法为 f(n-1,k-1) ; n nn k kn ??????????????n 2 211,且 6 (5) 若 n1>1, 则其分法为 f(n-k,k )。 nn nnnnnn nnn k kk kkn ''1 '2 '21 '1 211 1,1,1 0)1()1()1( ???????????????????????????则, 记??????????????????????knkknfknf knk knf kn knk knf *2),()1,1( *2 )1,1( 0 1 1),( 或7 整数划分问题(版本 2) 在正整数 n的所有不同的划分中,将最大加数 n1 不大于 m 的划分个数记作 q(n,m )。我们可以建立如下的递归关系。(1) q(n,1)=1, n>=1 ; 当最大加数 n1 不大于 1时,任何正整数 n只有一种划分形式,即: n=1+1+ ……+1 。(2) q(n,m )= q(n,n ), m>=n ; 最大加数 n1 实际上不能大于 n。因此, q(1,m)=1 。(3) q(n,n )=1+q(n,n-1) ; 正整数 n的划分有 n1=n 的划分和 n1<=n-1 的划分组成。(4) q(n,m )=q(n,m-1)+q(n-m,m) , n>m>1; n 的最大加数 n1 不大于 m的划分由 n1=m 的划分和 n1<=m-1 的划分组成。 8 ???????????????????1),()1,( )1,(1 ),( 11 1),(mnmmnqmnq mn nnq mn nnq mn mnq 或 Function q(n,m:integer):integer ; Begin if(n <1)or(m<1) then exit(0); if(n =1)or(m=1) then exit(1); if n<m then exit(q(n,n )); if n=m then exit(q(n,m-1)+1); exit(