递归算法x(x(8))(设有一个递归算法如下 int x (int n) { if (n<=3) return 1; else return x(n-2)+x(n-4)+1; })
本文目录
- 设有一个递归算法如下 int x (int n) { if (n<=3) return 1; else return x(n-2)+x(n-4)+1; }
- C语言递归算法
- 5. 设有一个递归算法如下 int x (int n) { if (n<=3) return 1; else return x(n-2)+x(n-4)+1; }
- 插入排序的递归算法
- 计算X(X(8))时需要计算X函数 为几次 为什么是18次
- 用递归法求8的阶乘,急急急!谢谢
- 设计递归算法x(x(8))需要调用几次函数x(int n)求详细~
设有一个递归算法如下 int x (int n) { if (n<=3) return 1; else return x(n-2)+x(n-4)+1; }
#include《stdio.h》#include《malloc.h》int count = 0;int x (int n){count = count + 1;printf("%d n = %d\n", count, n);if (n《=3){return 1;}else{return x(n-2)+x(n-4)+1;}}int main(void){x(x(8));return 0;}
C语言递归算法
本人学c++,c的语法已经淡忘了,但是递归不管什么语言都是一个原理其实简单一点来说就像数学里面的数列的通项公式:例如一个数列是2,4,6,8,10......很容易就可以得到通项公式是a=2*n n是大于0的整数你肯定学过这个数列的另外一种表示方式就是: a+2 n是大于1的整数其实这就是一个递归的形式,只要你知道初始项的值,未知项和前几项之间的关系就可以知道整个数列。程序例子:比如你要得到第x项的值普通循环:for(int i=1; i《=n; i++) if (i == x) cout 《《 2*i; /*cout 相当于 c里面的printf,就是输出.*/递归:int a(int x) { if (x = 1) return 2; /* 第一项那肯定是2了,这个也是递归的终止条件! */ else return a(x-1)+2; /* 函数自身调用自身是递归的一个特色 */比如x=4,那么用数学表示就是a(4)=a(3)+2=(a(2)+2)+2=((a(1)+2)+2)+2其实递归方法最接近自然,也是最好思考的一个方法,难点就是把对象建模成递归形式,但是好多问题本身就是以递归形式出现的。普通递归就是数据结构上的堆栈,先进后出。例如上面x=4,把a(4)放入栈底,然后放入a(3),然后a(2),a(1),a(1)的值已知,出栈,a(1)=2,a(2)出栈a(2)=a(1)+2=2+2=4,a(3)出栈a(3)=a(2)+2=(a(1)+2)+2=6,a(4)出栈a(4)=a(3)+2=(a(2)+2)+2=((a(1)+2)+2)+2=8再比如楼上的阶乘例子,当n=0 或 1时,0!=1,1!=1,这个是阶乘的初始值,也是递归的终止条件。然后我们知道n!=n*(n-1)!,当n》1时,这样我们又有了递归形式,又可以以递归算法设计程序了。(楼上已给出谭老的程序,我就不写了)。我给出一种优化的递归算法---尾递归。从我给出的第一算法可以看出,先进栈再出栈,递归的效率是很低的。速度上完全比不上迭代(循环)。但是尾递归引入了一个新的函数参数,用这个新的函数参数来记录中间值.普通递归阶乘fac(x),就1个x而已,尾递归用2个参数fac(x,y),y存放阶乘值。所以谭老的程序就变成// zysable’s tail recursive algorithm of factorial.int fac(int x, int y) { if (x == 1) return y; else return fac(x-1, y*x);}int ff(int x) { if (x == 0) return 1; else return fac(x,1);}对于这个程序我们先看函数ff,函数ff其实是对fac的一个封装函数,纯粹是为了输入方便设计的,通过调用ff(x)来调用fac(x,1),这里常数1就是当x=1的时候阶乘值了,我通过走一遍当x=3时的值即为3!来说明一下。首先ff(3),x!=0,执行fac(3,1).第一次调用fac,x=3,y=1,x!=1,调用fac(x-1,y*x),新的x=2,y=3*1=3,这里可以看到,y已经累计了一次阶乘值了,然后x还是!=1,继续第三次调用fac(x-1,y*x),新的x=1,y=2*3=6,然后x=1了,返回y的值是6,也就是3!.你会发现这个递归更类似于迭代了。事实上我们用了y记录了普通递归时候,出栈的乘积,所以减少了出栈后的步骤,而且现在世界上很多程序员都在倡议用尾递归取消循环,因为有些在很多解释器上尾递归比迭代稍微效率一点.基本所有普通递归的问题都可以用尾递归来解决。一个问题以递归来解决重要的是你能抽象出问题的递归公式,只要递归公式有了,你就可以放心大胆的在程序中使用,另外一个重点就是递归的终止条件;其实这个终止条件也是包含在递归公式里面的,就是初始值的定义。英文叫define initial value. 用普通递归的时候不要刻意让自己去人工追踪程序,查看运行过程,有些时候你会发现你越看越不明白,只要递归公式转化成程序语言正确了,结果必然是正确的。学递归的初学者总是想用追踪程序运行来让自己来了解递归,结果越弄越糊涂。如果想很清楚的了解递归,有种计算机语言叫scheme,完全递归的语言,因为没有循环语句和赋值语句。但是国内人知道的很少,大部分知道是的lisp。好了,就给你说到这里了,希望你能学好递归。PS:递归不要滥用,否则程序极其无效率,要用也用尾递归。by 一名在美国的中国程序员zysable。
5. 设有一个递归算法如下 int x (int n) { if (n<=3) return 1; else return x(n-2)+x(n-4)+1; }
18次,调用需要9次;x(9)调用9次,加在一起共18次。
递归函数在调用自身后直接传回其值,而不对其再加运算。尾部递归与循环是等价的,而且在一些语言可以被优化为循环指令。 因此,在这些语言中尾部递归不会占用调用堆栈空间。
既然在这里函数不能调用其自身,我们可以用 Z 组合子应用这个函数后得到的函数再应用需计算的参数。
扩展资料:
数据类型可以通过递归来进行定义,比如一个简单的递归定义为自然数的定义:“一个自然数或等于0,或等于另一个自然数加上1”。
这一定义相当于宣告“一个链表或是空串列,或是一个链表之前加上一个字符串”。可以看出所有链表都可以通过这一递归定义来达到。
插入排序的递归算法
插入排序算法: C版本的分析如下://直接插入排序:从小到大排;//算法说明: 比如说现在排序进行到第 i位了,那么1 到 i-1位都已经为有序序列了;然后将 r处,一次循环结束,进入下次循环;void insSort( int r,int length) //传数组,和数组大小;{ // 数组下标从1 开始, 0号位为监视哨; int i=0,j=0; for(i=2;i《=length;++i) { r记录当前数据; j=i-1; while(r) //寻找合适的位置; { r; //依次迭代覆盖; j=j-1; } r; //晕,终于找到满足条件的地方了,赶紧钻入; }}大功告成! 希望能帮上你。。。
计算X(X(8))时需要计算X函数 为几次 为什么是18次
用二叉树来表示吧,先计算最里面的X(8),表示方法如图:
计算出来的值是9,执行的次数是9(看有多少个X()的表达式)
在计算最外层的X(),因为里层的返回值是9所以外层的表达式是X(9)
和刚才的表示方法一样
用递归法求8的阶乘,急急急!谢谢
// 考虑了0!=0public int JieC(int a){ if (a==0) return 1; else return a*JieC(a-1);}这边输入字数才能100字.所以不能贴全部的代码.调用这个函数就可以了.8以参数传进去.
设计递归算法x(x(8))需要调用几次函数x(int n)求详细~
这个题我觉得主要还得看x()里的递归语句那里怎么写,假如递归调用那里每次是n-1,并且n=1的时候停止递归(有返回值),那么:x(x(8)) --》x(x(7)) --》x(x(6)) --》x(x(5)) --》x(x(4)) --》x(x(3)) --》x(x(2)) --》x(x(1)) --》到x(1)的时候返回一个确定的值,假如返回了1,那么加上外层的x(1),调用了x(int n)9次,如果递归条件或停止递归的条件变了,调用次数也会变化;。
更多文章:
百忧解和舍曲林哪个好(请问氟西汀和舍曲林哪个抗抑郁效果更好)
2024年3月1日 19:40
easyui隐藏textbox(判断easyUI的控件是否为隐藏状态)
2024年7月24日 08:54
怎么用浏览器打开DTD文件?在DTD文件和XML文件中的注释符各是什么
2024年5月6日 01:21
eclipse代码字体大小设置快捷键(myeclipse切换大小的快捷键是什么,比较常用的还有什么)
2024年7月11日 08:16
resample pandas(pandas resample 怎么实现)
2024年7月16日 02:43
java编程思想要怎么看(java编程思想该怎么看 哪部分重要)
2024年6月7日 22:13
lostfocus(Vb里Validate和Lostfocus有什么区别)
2024年7月15日 11:17
import的名词(clean import loan 和 import facilities 的区别)
2024年7月20日 19:47
c语言函数递归求阶乘(关于c语言用递归计算阶乘 麻烦详细说明)
2024年8月19日 22:15
xml文件头(Android报错 Content is not allowed in prolog)
2024年5月27日 11:11