文档介绍：该【递归与分治策略讲义课件 】是由【zhangkuan14314】上传分享，文档一共【64】页，该文档可以免费在线阅读，需要了解更多关于【递归与分治策略讲义课件 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。第2章递递归归与分分治策策略
Recursion,divideandconquermethod
学****要要点:
理解递递归的的概念念。
掌握设设计有有效算算法的的分治治策略略。
通过下下面的的范例例学********分治治策略略设计计技巧巧。
(1))二分分搜索索技术术;
(2))合并并排序序
(3)快速速排序序;
(4)最接接近点点对问问题;;
递归(recursion)是数学学与计计算机机科学学中的的基本本概念念。直直接或或间接接地调调用自自身的的算法法称为为递归归算法法。用用函数数自身身给出出定义义的函函数称称为递递归函函数。。
递归程程序不不能无无限制制地自自我调调用,,否则则就会会永不不终止止,递递归程程序必必须有有终止止条件件。
尽管递递归程程序在在执行行时间间上往往往比比非递递归程程序要要付出出更多多的代代价,,但有有很多多问题题的数数学模模型或或算法法设计计方法法本来来就是是递归归的,,用递递归过过程来来描述述它们们不仅仅非常常自然然,而而且且证明明该算算法的的正确确性要要比相相应的的非递递归形形式容容易得得多,,因此此递归归不失失为一一种强强有力力的程程序设设计方方法。。
构成递递归需需具备备的条条件:
,,须有有个出出口,,化简简为非非递归归状况况处理理(边界条条件);,且更为为简单单(递归模模式).
递归程程序的的书写写方式式:
Procedure<name>(parameterlist)
if<initialcondition>
return(initialvalue);
else
return(<name>(parameterexchange));
end
例1阶乘函函数
阶乘函函数可可递归归地定定义为为:
边界条条件
递归方方程
边界条条件与与递归归方程程是递递归函函数的的二个个要素素,递递归函函数只只有具具备了了这两两个要要素,,才能能在有有限次次计算算后得得出结结果。。
intfactorial(intn)
{
if(n==0)return1;
returnn*factorial(n-1);
}
例2Fibonacci(斐波那那齐)数列
无穷数列1,1,2,3,5,8,13,21,34,55,……,称为Fibonacci数列。它可可以递归地地定义为::
边界条件
递归方程
第n个Fibonacci数可递归地地计算如下下:
intfibonacci(intn)
{
if(n<=1)return1;
returnfibonacci(n-1)+fibonacci(n-2);
}
斐波那齐数数列算法的的递归结构构(n=5)
递归程序结结构清晰,,可读性强强,而且容容易用数学学归纳法来来证明算法法的正确性性,因此它它为设计算算法、调试试程序带来来很大方便便。
递归算法的的运行效率率较低,无无论是耗费费的计算时时间还是占占用的存储储空间都比比非递归算算法要多。。
求斐波那齐齐数列的非递归程序序:
voidfibonacci(intn)
{intprev,now,next,j;
if(n<=1)return(1);else
{prev=1;
now=1;
for(j=2;j<=n;j++)
{
next=prev+now;
prev=now;
now=next;
}return(next);
}
}
使用递归子子程序时,,最好以较较难的问题题为主,将将处理栈的的复杂问题题全交给编编译程序去去处理。
具有编译递递归程序能能力的程序序设计语言言有:C、Pascal、ALGOL、PL/A、ADA、QBASIC等,不具有有编译递归归程序能力力的程序设设计语言有有:FORTRAN、COBOL、BASIC、低级语语言。
前2例中的函数数都可以找找到相应的的非递归方方式定义::
例1阶乘函数
例2Fibonacci(斐波那那齐)数列列
例3Hanoi塔问题
设x,y,z是3个个塔座。开开始时,在在塔座x上上有一叠共共n个圆盘盘,这些圆圆盘自下而而上,由大大到小地叠叠在一起。。各圆盘从从小到大编编号为1,2,…,n,现要要求将塔座座x上的这这一叠圆盘盘移到塔座座z上,并并仍按同样样顺序叠置置。在移动动圆盘时应应遵守以下下移动规则则:
规则1:每每次只能移移动1个圆圆盘;
规则2:任任何时刻都都不允许将将较大的圆圆盘压在较较小的圆盘盘之上;
规则3:在在满足移动动规则1和和2的前提提下,可将将圆盘移至至x,y,z中任一一塔座上。。
x
y
z