文档介绍：递归与回溯算法
捐掣佰邻薯湘汗于颤启云浆掳阎癌历曝箍姻毅焉涌缔宅稠歉柿喳利旭向钦递归与回溯算法递归与回溯算法
1
递归的定义:
在定义一个过程或函数时出现调用本过程或本函数的成分,称为递归。若调用自身,称为直接递归。若过程或函数p调用过程或函数q,而q又调用p,则称为间接递归。
在程序设计中,使用递归技术往往使函数的定义和算法的描述简洁且易于理解。
递归的使用:
Function jiech(n:integer):longint;
Begin
if n=0 then jiech:=1
else jiech:=n*jiech(n-1);
End;
打边筋己粱笔之矮途萍腊砍将旭颠塞捞艺丛陛岗辑见茫物洪扬怔灭挤八佃递归与回溯算法递归与回溯算法
2
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,则有:
峰拜亡斤凰拎弧灸匿身烃阳牌忆林隔埂含良忻霹道种丸孤惫蛹俺原戳避垮递归与回溯算法递归与回溯算法
3
,采用递归的方法编写算法既方便又有效。如单链表:
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;
栓跋菏安忽踌压幽汝辰李醋镊彻轨辱抡炼政慰薛涅萎吹柱确攫抉质桌炬滞递归与回溯算法递归与回溯算法
4
例:整数划分问题(版本1)
为避免重复,记
设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);
痪郊休鳞辫侣急忻序患纺寇肛合捌蜘搐仕许揽摸纲峻烹哨判拎货糟车窥熔递归与回溯算法递归与回溯算法
5
(5)若n1>1,则
其分法为f(n-k,k)。
备现案马岗浇辣呸扒蜀雹麓阉瑚涛磊婚淋急闯懒烫阉赵霍稳锨梗巫驮仔翠递归与回溯算法递归与回溯算法
6
整数划分问题(版本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的划分组成。
心杭琶掐曼喜峨捍蔡仪姨缮午奴筒赵控稀头汗苍蓖萤同麦恩吵瘟皖抨咽汉递归与回溯算法递归与回溯算法
7
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(q(n,m-1)+q(n-m,m));
End;{正整数n的划分数p(n)=q(n,n)。}
乖粱投斩院婚蚁喳施莽披佐皑妇诽荐徘瓷此炳另杰岸角府塌悼泛菩晦佰彼递归与回溯算法递归与回溯算法
8
递归过程或函数直接(或间接)调用自身,但如果仅有这些操作,那么将会由于无休止地调用而引起死循环。因此一个正确的递归程序虽然每次调用的是相同的子程序,但它的参数、输入数