《C++递归函数》PPT课件.ppt

《《C++递归函数》PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、递归函数递归概念设计方法步骤执行过程递归与迭代典型案例【引例1】赏麦粒国际象棋发明人西萨·班·达依尔在国王问赏时说：“陛下，请您在这张棋盘的第1个小格里赏给我一粒麦子，在第2个小格里给2粒，第3个小格给4粒，以后每一小格都比前一小格加一倍。请您把这样摆满棋盘上所有64格的麦粒……”?需要多少粒麦子f(1)=1;f(2)=2;f(3)=4;……f(n)=2*f(n-1);f(64)=264-1=18446744073709551615什么特点？【引例2】汉诺塔问题大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令

2、婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。解决方法要实现将64个圆盘从第一根柱子移到第三根柱子，首先要完成将最上面的63个圆盘移到第二根柱子上，然后再将最下面的一个圆盘移到第三根柱子上。这样，如何移动64个圆盘的问题就转换成了如何移动63个圆盘问题，依次类推，解决问题的规模可以逐步降低为解决移动62、61、60……3、2、1个圆盘的问题。以上两个例子都是递归问题一、递归的概念1、定义2、特点3、典型类型1、定义递归方法是指通过函数或过程调用自身，将问题转化为本质相同但规模较小的子

3、问题的方法。如果是直接调用自身，称为直接递归；如果是通过其它函数或过程间接调用自身，则称为间接递归。递归方法是算法和程序设计中的一种重要技术，是许多复杂算法的基础。A(){……A();……}A(){……B();……}B(){……A();……}直接递归间接递归2、特点原始问题可转化为解决方法相同的新问题；新问题的规模比原始问题小；新问题又可转化为解决方法相同的规模更小的新问题，直至终结条件为止。3、典型类型问题定义是递归的如，阶乘的定义：(n=0)(n>0)n!=写成函数形式则为：(n=0)(n>0)f(n)=这种函数定义形式是用阶乘函数自己本身定义了自身，故是一

4、种递归定义。数据结构是递归的如前面介绍的链表的结点结构定义：structnode{intdata;structnode*next;}其中，指针域next是指向自身类型的指针，故该数据结构是一种递归数据结构。对于递归数据结构，采用递归方法编写算法简单有效。如：intsum(node*head){if(head==NULL);elsereturn(head->data+);}以上函数用递归算法实现了求解以head做表头指针的链表的所有结点数据的和。return0sum(head->next)问题求解过程是递归的如，前面数组一章中介绍的在有序数组中查找某一数据是否存在

5、于数组中的折半查找算法，其求解过程便是一个递归求解的过程。即不断在前一次区间一半的搜索区间范围内重复着与前一次搜索相同的操作。具体实现后面给出。二、设计方法步骤基本思想：将一复杂问题分解成若干简单且相同的子问题，这样较为复杂的原问题就转换为简单的子问题，而简单到一定程度的子问题可以直接求解，则原问题可递推得到解。递归算法所需条件：存在递归结束条件及结束时的值能用递归形式表示，且递归向终止条件发展递归模型：递归模型是递归算法的抽象，反映递归问题的递归结构。以阶乘求解为例，其对应的递归模型为：fun(0)=1(1)fun(n)=n*fun(n-1)n>0(2)式子（

6、1）给出了递归的终止条件，被称为递归出口；式子（2）给出了fun(n)与fun(n-1)之间的关系，被称为递归体。设计步骤：描述递归关系确定递归出口写出递归函数intf(intn){if(n==0)return(1);else;}return(n*f(n-1))intfac(intn){if(n==1)return(1);elsereturn(fac(n-1)*n);}voidmain(){inty;y=f(4)cout<

7、eturn(fac(n-1)*n);}intfac(intn){if(n==1)return(1);elsereturn(fac(n-1)*n);}intfac(intn){if(n==1)return(1);elsereturn(fac(n-1)*n);}intfac(intn){if(n==1)return(1);elsereturn(fac(n-1)*n);}第一次调用：n为4第二次调用：n为3第三次调用：n为2第四次调用：n为1三、执行过程返回1返回1*2返回1*2*3返回1*2*3*4分解?递归函数反映一种什么样的思维问题小问题n!(n-1)

8、!问题分解小问题更小