文档介绍：1 1递归与回溯算法递归与回溯算法山东省实验中学山东省实验中学王乃广王乃广 2 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 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 4 整数划分问题为避免重复,记 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,且 5 5 (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),( 或 6 6 递归过程或函数直接(或间接)调用自身,但如果仅有这些操作,那么将会由于无休止地调用而引起死循环。因此一个正确的递归程序虽然每次调用的是相同的子程序,但它的参数、输入数据等均有所变化,并且在正常的情况下,随着调用的深入,必定会出现调用到某一层时,不再执行调用而是终止函数的执行。递归思路是把一个不能或不好直接求解的“大问题”转化成一个或几个“小问题”来解决,再把这些“小问题”进一步分解成更小的“小问题”来解决,如此分解,直至每个“小问题”都可以直接解决。递归分解不是随意地分解,要保证“大问题”和“小问题”相似。例:采用递归算法求实数数组 A[0..n] 中的最小值。 7 7 算法 1:设 f(a,i )为数组元素 a[0]..a[i] 中的最小值。当 i=0 时, 有 f(a,i )=a[0] ;假设 f(a,i-1) 已求出,则: ?????? 其他情况时当])[ ),1,( min( 0 ]0[),(iaiaf i aiaf算法 2:设 f(i,j )为 a[i]..a[j ]中的最小值。将 a[0]..a[n] 看作一个线性表,它可以分解成 a[0]..a[i] 和 a[i+1]..a[n] 两个子表, 分别求得各自的最小值 x和y,较小者就是 a[0]..a[n] 中的最小值。而求解子表中的最小值方法与总表相同,即再分别把它们分成两个更小的子表,如此不断分解,直到表中只有一个元素为止(该元素就是该表中的最小值)。 8 8 function min(i,j:integer):real ; var mid:integer ; min1,min2:real; begin if i=j then min:= a[i ] else begin mid:=( i+j ) div 2; min1:= min(i,mid ); min2:=min(mid+1,j); if min1<min2 then min:=min1