文档介绍：递归与回溯算法
山东省实验中学王乃广
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
整数划分问题
为避免重复,记
设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);
4
(5)若n1>1,则
其分法为f(n-k,k)。
5
递归过程或函数直接(或间接)调用自身,但如果仅有这些操作,那么将会由于无休止地调用而引起死循环。因此一个正确的递归程序虽然每次调用的是相同的子程序,但它的参数、输入数据等均有所变化,并且在正常的情况下,随着调用的深入,必定会出现调用到某一层时,不再执行调用而是终止函数的执行。
递归思路是把一个不能或不好直接求解的“大问题”转化成一个或几个“小问题”来解决,再把这些“小问题”进一步分解成更小的“小问题”来解决,如此分解,直至每个“小问题”都可以直接解决。
递归分解不是随意地分解,要保证“大问题”和“小问题”相似。
例:采用递归算法求实数数组A[0..n]中的最小值。
6
算法1:设f(a,i)为数组元素a[0]..a[i]中的最小值。当i=0时,有f(a,i)=a[0];假设f(a,i-1)已求出,则:
算法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]中的最小值。而求解子表中的最小值方法与总表相同,即再分别把它们分成两个更小的子表,如此不断分解,直到表中只有一个元素为止(该元素就是该表中的最小值)。
7
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
else min:=min2;
end;
end;
8
汉诺塔问题:
有n个半径各不相同的圆盘,按半径从大到小,自下而上依次套在A柱上,另外还有B、C两根空柱。要求将A柱上的n个圆盘全部搬到C柱上去,每次只能搬动一个盘子,且必须始终保持每根柱子上是小盘在上,大盘在下。输出总共移动的次数及移动方案。
A
B
C
9
分析:在移动盘子的过程当中发现要搬动第n个盘子,必须先将前n-1个盘子从A柱搬到B柱去,再将A柱上的最后一个盘子搬到C柱,最后从B柱上将n-1个盘子搬到C柱去。搬动n个盘子和搬动n-1个盘子时的方法是一样的,递归处理。当只需搬一个盘子时,直接搬动,不需要递归。
10