下载此文档

c语言递归算法及经典递归例子代码实现.docx


文档分类:IT计算机 | 页数:约16页 举报非法文档有奖
1/16
下载提示
  • 1.该资料是网友上传的,本站提供全文预览,预览什么样,下载就什么样。
  • 2.下载该文档所得收入归上传者、原创者。
  • 3.下载的文档,不会出现我们的网址水印。
1/16 下载此文档
文档列表 文档介绍
一、什么叫做递归?
一个过程或函数在其定义或说明中有直接或间接调用自身的一种方 法;递归函数就是直接或间接调用自身的函数,也就是自身调用自己;
刚接触递归的同学,可能难以理解递归,难以理解的点可能很多,例如:
1 .函数为什么可以在自己的内部又调用自己呢?
既然可以自己调用自己,那么递归运行过程中一定回有很多层相互嵌 套,到底什么时候不再嵌套呢?
递归运行过程中,相互嵌套的多层之间会有参数传递,多层之间是否 会相互影响?
递归两个要素
递归边界
递归的逻辑——递归"公式"
递归的过程一定有参数的变化,并且参数的变化,和递归边界有关系.
在难度较大的题目中,这两者均不容易直接得到.
递归的种种问题,也许理解的同学可能可以用一句话解释清楚,但是不 理解的同学再怎么说也没办法理解, 下面通过几个简单的例子【体会】一下递归,先从【感性】的角度理解 递归.
Fibonacci 数
我们直到Fibonacci数的递推公式为:
F(0)=F(l)=1,F(n) = F(n-l) + F(n-2) n>=2;
这个明显地给出了递归边界n=0或1的时候F(n)的值,和递归逻辑
F(n) = F(n-l) + F(n-2),即递推公式.所以这个递归函数不难书写 #include<iostream>using namespace std;
int F(int n)〃函数返回一个数对应的Fibonacci数{ if (n==0 | | n==l)//递归边界
return 1; return F(n-l) + F(n-2);//递归公式}
int main()( 〃测试
endl;
int n; while(cin >> n) cout << F(n) <<
return 0;
}
阶乘阶乘的递归公式为:
1
F(n)= < n
代码如下:
#include<iostream>using namespace std;
int F(int n){
if(n==0)//递归边界
return 1;
return n*F(n-l);//递归公式}
int main()(
int n;
cin >> n; cout << F(n) << endl;
return 0;
3.数组求和
给一个数组a[]:a[O],a[l],...,a[n-l]如何用递归的方式求和? 仍然是两个问题:递归边界和递归公式.
递归边界是什么?一时不容易想到,但是我们想到了求和,多个数的求 和过程是什么,x,y,z,w手动求和的过程是什么?步骤如下:
x+y=a,任务变为a,z,w求和
a+z=b,任务变为b,w求和
b+w=c得出答案
思考一下,【得出答案】这一步为什么就可以得出答案呢?(废话?)是 因为,一个数不用相加就能得出答案.
所以,递归的边界就是只有一个数.
所以,递归边界有了,那么递归公式呢?其实手动计算过程中,隐含了 递归公式:
设有n个数%,%,・・・,%,试求和.
尸(《,%,•••,[〃)=。[+尸(。2,,・皿3
其中+为求两个数的和,F为求多个数的和的递归函数代码如下:
#include<iostream>using namespace std;
int F(int a[]int start,int end)( if(start==end)//递归边界
return a[start];
return a[start] + F(a,start+l,end);〃递归公式}
cout << F(a,s,e) <<
int main()( int a[] = {1,2,3,4,5}; int s=0,e=4;
endl;
return 0;
)
知乎@编建学****br/>4.求数组元素最大值
手动求最大值的过程是什么,遍历+比较,过程如下:
例如,求326,7,2,4的最大值:先设置最大值max=-999999 ,然后将 max和数组元素逐个(遍历)比较如果a[i]>max,则更新max的值为 a[i],否则max不变,继续向后遍历,直到遍历结束.
max<3 ,则 max=3
max>2 , max=3 不变
max<6 ,则 max=6
max<7 ,则 max=7
max>2 , max=7 不变
max>4 , max=7 不变
遍历结束,max=7为最大值.
和求和类似,递归的公式如下: 设有n个数《a,...,%,试最大值.
尸(。1,I?,..., [〃)= max(nl,F(u2

c语言递归算法及经典递归例子代码实现 来自淘豆网www.taodocs.com转载请标明出处.

相关文档 更多>>
非法内容举报中心
文档信息
  • 页数16
  • 收藏数0 收藏
  • 顶次数0
  • 上传人ttteee8
  • 文件大小357 KB
  • 时间2022-06-22