c++递归函数
33页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片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。,解决方法 要实现将64个圆盘从第一根柱子移到第三根柱子,首先要完成将最上面的63个圆盘移到第二根柱子上,然后再将最下面的一个圆盘移到第三根柱子上。这样,如何移动64个圆盘的问题就转换成了如何移动63个圆盘问题,依次类推,解决问题的规模可以逐步降低为解决移动62、61、603、
2、2、1个圆盘的问题。,以上两个例子都是递归问题,一、递归的概念 1、定义 2、特点 3、典型类型,1、定义 递归方法是指通过函数或过程调用自身,将问题转化为本质相同但规模较小的子问题的方法。如果是直接调用自身,称为直接递归;如果是通过其它函数或过程间接调用自身,则称为间接递归。递归方法是算法和程序设计中的一种重要技术,是许多复杂算法的基础。,A( ) A( ); ,直接递归,间接递归,2、特点 原始问题可转化为解决方法相同的新 问题; 新问题的规模比原始问题小; 新问题又可转化为解决方法相同的规模更小的新问题,直至终结条件为止。,3、典型类型,问题定义是递归的 如,阶乘的定义:,写成函数形式则为:,这种函数定义形式是用阶乘函数自己本身定义了自身,故是一种递归定义。,数据结构是递归的 如前面介绍的链表的结点结构定义: struct node int data; struct node *next; 其中,指针域next是指向自身类型的指针,故该数据结构是一种递归数据结构。,对于递归数据结构,采用递归方法编写算法简单有效。如: int sum(node *head) if(head=NUL
3、L) ; else return(head-data+ ); 以上函数用递归算法实现了求解以head做表头指针的链表的所有结点数据的和。,return 0,sum(head-next),问题求解过程是递归的 如,前面数组一章中介绍的在有序数组中查找某一数据是否存在于数组中的折半查找算法,其求解过程便是一个递归求解的过程。即不断在前一次区间一半的搜索区间范围内重复着与前一次搜索相同的操作。具体实现后面给出。,二、设计方法步骤 基本思想: 将一复杂问题分解成若干简单且相同的子问题,这样较为复杂的原问题就转换为简单的子问题,而简单到一定程度的子问题可以直接求解,则原问题可递推得到解。 递归算法所需条件: 存在递归结束条件及结束时的值 能用递归形式表示,且递归向终止条件发展,递归模型:,递归模型是递归算法的抽象,反映递归问题的递归结构。以阶乘求解为例,其对应的递归模型为: fun(0)=1 (1) fun(n)=n*fun(n-1) n0 (2) 式子(1)给出了递归的终止条件,被称为递归出口;式子(2)给出了fun(n)与fun(n-1)之间的关系,被称为递归体。,设计步骤:,描述递归关系
4、确定递归出口 写出递归函数,int f(int n) if (n=0) return(1); else ; ,return(n*f(n-1),int fac(int n) if(n=1) return(1); else return(fac(n-1)*n); ,void main() int y; y=f(4) couty; ,? 为什么能计算n! 考察程序执行过程:(分为递推和回归两个过程),三、执行过程,返回1,返回1*2,返回1*2*3,返回1*2*3*4,分 解,? 递归函数反映一种什么样的思维,问题,小问题,n!,(n-1)!,问题,分 解,小问题,更小 问题,最小 问题,分 解,分 解,不能再分解,n!,(n-1)!,(n-2)!,1!,四、递归与迭代,用迭代法求n! s=1; for(i=1;i=n;i+) s=s*i; 迭代过程: 1!=1 2!=1!*2 3!=2!*3 n!=(n-1)!*n,1.迭代与递归的区别? 迭代:自下向顶的计算过程 1!=1 2!=1!*2 3!=2!*3 n!=(n-1)!*n 递归:自顶向下逐步分解问题,最后自下向顶计算 递推 回归,2
《c++递归函数》由会员简****9分享,可在线阅读,更多相关《c++递归函数》请在金锄头文库上搜索。
2019年自贡市清华园学校高考生物简单题专项训练(含解析)
2019年秋季石油大学现代应用文写作网考练习试题+在线作业答案
2019年信宏中学高考生物简单题专项训练(含解析)
2019年莲塘中学高考生物简单题专项训练(含解析)
2019年宜阳县二中高考生物简单题专项训练(含解析)
2019年宁波神舟学校高考生物简单题专项训练(含解析)
2019年谢通门县中学高考生物简单题专项训练(含解析)
2019年前埔中学高考生物简单题专项训练(含解析)
2018年二级建造师公路工程实务重点考点总结
2018年一级建造师水利水电实务考点重点
2019年一级建造师市政实务案例考点
概率论与数理统计第二版谢永钦课后答案
空间向量求角度与距离10种题型归类 (解析版)2023-2024学年高二数学上学期期中期末复习讲练测(人教A版2019选择性必修第一册)
中医综合模拟试卷348
2011年3000名教师及特岗招考《计算机基础》复习题
2019年槎水中学高考生物简单题专项训练(含解析)
2009年9 月全国计算机等级考试二级笔试试卷
2019年宣城市第四中学高考生物简单题专项训练(含解析)
中医综合模拟试卷333
2019年安全知识竞赛题库2
2024-01-31 15页
2024-01-31 21页
2024-01-31 37页
2024-01-31 30页
2024-01-31 22页
2024-01-31 48页
2024-01-31 32页
2024-01-31 40页
2024-01-31 31页
2024-01-31 20页