算法设计与分析(二).ppt

算法设计与分析(2011级ACM创新实验班)
1
二、递归与递归式
递归与递归程序设计
1. 什么是递归？
递归是一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法。
1）递归的本质
递归把一个大型、复杂的问题层层转化为一个与原问题相似、但规模较小的问题来求解，只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。
2
2）递归的结构
一般来说，递归由边界条件、递归计算和递归返回组成。当边界条件不满足时，递归向前推进计算过程；当边界条件满足时，递归返回。
2. 递归程序设计
程序调用自身的编程技术称为递归程序设计。是递归算法的直接描述。
关于递归，注意两点：
(1) 递归就是在过程或函数里直接或简接地调用自身;
(2) 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口，否则会产生死循环而出错。
3
斐波那契(Fibonacci)序列：
F0 = F1 = 1
Fi = Fi-1 + Fi-2 （i>1)
求斐波那契数：
procedure F(n)
//返回第n个斐波那契数//
integer n
if n ≤ 1 then return(1)
else return(F(n-1) + F(n-2))
endif
end F
思考：上述算法的效率非常低下，为什么？
4
上述过程的效率很差，存在大量的重复计算：
改进：保存中间结果（递推模型）
其它递归模型
F(n)
F(n-1)
F(n-2)
F(n-2)
F(n-3)
F(n-3)
F(n-4)
分析：F(n-2)被算了两次，F(n-3)被算了三次，F(n-4)被算了五次，.......，总的运算量为这些运算之和，所以，事实上，这样的计算过程，运算次数本身也是一个斐波那契数列。整个计算的时间复杂度约为O()。非常之大！
5
欧几里得算法
已知两个非负整数a和b，且a＞b≥0，求这两个数的
最大公因数。
辗转相除法：若b=0，则a和b的最大公因数等于a；若b＞0，则a和b的最大公因数等于b和用b除a的余数的最大公因数。
求最大公因数
procedure GCD(a,b) // 约定a>b //
if b=0 then return(a)
else return (GCD(b,a mod b))
endif
end GCD
例： GCD(22,8) = GCD(8,6) = GCD(6,2) = GCD(2,0) = 2
6
用递归策略设计的检索算法
已知元素x和元素表A（1：n），判断x是否等于A中
某元素的值。
在A（1：n）中检索x
procedure SEARCH(i)
//如果在A（1：n）中有一元素A(k)=x，则将其第一次出现的下标k返回，否则返回0//
global n,x,A(1:n)
case
:i>n: return(0)
:A(i) = x; return(i)
:else: return(SEARCH(i+1))
endcase
end SEARCH
7
递归是一种强有力的设计方法
与数学模型一致
表述简单、清晰、代码量少
可读性强、容易证明正确性
递归的问题：执行时间长、运行效率低，特别是占用空间多，容易造成系统栈的溢出。
主要原因：递归调用时有大量的现场保护与恢复操作，需要时间处理；在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储，递归层次数过多容易造成栈溢出等。
8
3. 怎么克服递归的效率问题？
—— 化递归为递推
递归：递归是一种从上至下的“分解求解“的过程，即不断地把大问题分解为小问题，直到小问题规模足够小，然后求解并进行递归返回和结果合并。——效率差！
递推：递推是一种从下往上的“合并求解“过程，即从解决小问