洛阳网站排名企业信用信息公示系统广东

当前位置： 首页 > news >正文

洛阳网站排名,企业信用信息公示系统广东,wordpress会员功能主题,app关键词排名优化本文主要讲解的是c语言函数递归的知识点 目录 基础概念 什么是递归#xff1f; 递归的条件 递归的优点和缺点 举例 1、死循环 2、n的阶乘 3、求n的k次方 4、打印一个数的每一位 应用 斐波那契数列 青蛙跳台问题 汉诺塔问题 基础概念 什么是递归#xff1f; 递归… 本文主要讲解的是c语言函数递归的知识点 目录 基础概念 什么是递归 递归的条件 递归的优点和缺点 举例 1、死循环 2、n的阶乘 3、求n的k次方 4、打印一个数的每一位 应用 斐波那契数列 青蛙跳台问题 汉诺塔问题 基础概念 什么是递归 递归是一种算法或函数调用自身的过程。在递归过程中问题被分解为规模更小的同类问题的子问题直到达到终止条件。 简单来讲递归就是递推回归函数自己调用自己的过程就是递归。 递归的条件 1. 将问题转化为其子问题子问题要与原问题具有相同的解法。      递归存在限制条件当满足这个限制条件的时候递归便不在继续。  2. 递归的出口每次递归调用之后越来越接近这个限制条件。 递归的优点和缺点 优点 递归能够简化问题的解决过程使代码更加简洁和易读。递归能够将复杂的问题分解为更小的子问题从而降低问题的复杂度。递归能够提供一种优雅的解决方案特别是对于某些问题递归的思想更加自然和直观。 缺点 递归可能导致性能问题特别是在处理大规模问题时。递归的函数调用会占用额外的内存空间并且可能导致栈溢出。递归可能导致代码的执行效率较低特别是在处理重复计算的情况下。递归的函数调用可能会重复执行相同的计算步骤。递归可能导致代码的理解和调试变得困难。递归的执行过程比较隐式可能需要更多的思考和调试工作。 我们知道在c语言每一次函数调用都需要为本次函数调用在栈区申请空间来保存函数调用期间的各种局部变量的值这块空间称为运行时堆栈或者函数栈帧。 若函数不返回函数对应的栈帧空间就会一直占用所以当采用函数递归来完成代码当递归太深时就会浪费太多的栈帧空间可能会导致栈溢出Stack overflow。 具体的代码会在下面举例中详细解答。 举例 1、死循环 我们知道main()函数也是一个函数所以我们也可以在main()函数中调用它自己。 #includestdio.hint main() {printf(hhhhh\n);main();return 0; } 当我们调试时我们会遇到这种情况 这就是我们上面提到的栈溢出问题。 如何去理解呢 我们知道每一次函数调用都会在栈区里面上申请一块空间。 以上代码会产生死循环也就是说它会一直申请栈帧空间但并不会释放而栈区空间并不是无限大因此会产生栈溢出问题。 2、n的阶乘 一个正整数的阶乘factorial是所有小于及等于该数的正整数的积并且0的阶乘为1。自然数n的阶乘写作n!。 11 21*2 2*1!  31*2*3 3*2! 41*2*3*4 4*3! 51*2*3*4*5 5*4! … n!1*2*34……n n(n-1)! ; 根据以上规律我们可以写出代码 int Fac(int n) {if (n 0)return 1;return n * Fac(n - 1); } 3、求n的k次方 编写一个函数实现n的k次方使用递归实现。 n的1次方n n的2次方n*n n*n的1次方 n的3次方n*n*n n*n的2次方 n的4次方n*n*n*n n*n的3次方 … n的k次方 n*n*n……*n n*n的k-1次方 推导出n的k次方的规律可以写出代码 int Pow(int n, int k) {if(k0)return 1;else if(k1){return nPow(n, k-1);} } 4、打印一个数的每一位 递归方式实现打印一个整数的每一位 思路 N   N 9 Print(N)Print(N-1), 打印N print(n) print(n/10); printf(%d,n%10); 当我们给出一个数1234 print(1234): print(123);printf(%d,1234%10);                           |                           |                     print(12);printf(%d,123%10);                           |                           |                     print(1);printf(%d,12%10);                           |                           |                     print(%d,1%10);(19) 代码实现 void print(unsigned int n){if(n9)print(n/10);printf(%d , n%10);}应用 斐波那契数列 斐波那契数列Fibonacci sequence又称黄金分割数列因数学家莱昂纳多·斐波那契Leonardo Fibonacci以兔子繁殖为例子而引入故又称为“兔子数列”指的是这样一个数列1、1、2、3、5、8、13、21、34、……。在数学上斐波那契数列以如下被以递推的方法定义F(1)1, F(2)1, F(n)F(n - 1)F(n - 2)n ≥3n ∈ N。 思路 1 N 3               Fac(N) Fac(N-1) Fac(N-2)     N 3 代码 long long Fac(int N) {if(N 3)return 1;return Fac(N-1) Fac(N-2); } 当我们使用递归的方法来解决这个问题时 当n12, 3 ,4 25 等可以很快的得出结果但是当我们输入的n50时就会出现下面的情况 并没有结果显示那计算机到底有没有在计算呢我们查看一下任务管理器会发现它确实在计算只不过这个计算次数比较大。 那我们如果想要得到50甚至有大于50的斐波那契数列怎么去优化 1 1 2 3 5 8 13 21…… 令a1,b1; { cab; ab; bc; } 依次类推直至算到第n个数。 代码 long long Fib(int n) {long long a 1, b 1, c;int i 3;while (i n){c a b;a b;b c;i;}return b; }int main() {int n;scanf(%d, n);long long tFib(n);printf(%lld, t);return 0; } 运行结果 青蛙跳台问题 题目描述 一只青蛙跳一次只能跳1级台阶或跳2级台阶。   求:该青蛙跳上第n级台阶总共有多少种跳法 思路 当只有一个台阶时 青蛙只有一种跳法 当有两个台阶时 青蛙可以一次跳两个台阶也可以先跳一个台阶再跳一个台阶 当有三个台阶时 青蛙第一次有两种选择1、跳一个台阶 2、跳两个台阶 当选择1时青蛙还剩下两个台阶当只有两个台阶时我们已经得出是两种跳法 当选择2时青蛙还剩下一个台阶当只有一个台阶时我们已经得出是一种跳法 所以三个台阶的跳法是选择1选择23 当有四个台阶时 青蛙第一次有两种选择1、跳一个台阶 2、跳两个台阶 当选择1时青蛙还剩下三个台阶当有三个台阶时我们已经得出是三种跳法 当选择2时青蛙还剩下两个台阶当有两个台阶时我们已经得出是两种跳法 所以三个台阶的跳法是选择1选择25 同理 有n个台阶 jump(n)jump(n-1)jump(n-2); 代码实现 #includestdio.hint jump(int n) {if (n 1)return 1;if (n 2)return 2;return jump(n - 1) jump(n - 2); } int main() {int n;scanf(%d, n);int tjump(n);printf(%d, t); } 汉诺塔问题 汉诺塔Tower of Hanoi又称河内塔是一个源于印度古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定在小圆盘上不能放大圆盘在三根柱子之间一次只能移动一个圆盘。 思路下面内容是求移动需要的步骤并不包含每一步的步骤 当柱子上只有一个圆盘这种情况只需要一步就可以将圆盘移动到第三根石柱上 当柱子上有两个圆盘这种情况需要三步来移动圆盘 当柱子上有三个圆盘 第一步我们需要先将上面两个圆盘移动到第二根石柱 第二步再将最后的石柱移动到第三根 其中第一步和当柱子上有两个圆盘类似其步骤也是相同为3步第二步和当柱子上只有一个圆盘类似只需要1步。 第三步我们只需要将剩下的两个石柱移动到第三根上去其步骤和当柱子上有两个圆盘类似为3步 综上我们可以得出当柱子上有三个圆盘步骤3137 同理 当柱子上有n个圆盘 将n-1个圆盘移动到第二根石柱再将最后一个移动到第三根石柱 再将剩下的移动到第三根石柱 Hnt(n)2*Hnt(n-1)1; 代码实现 #includestdio.hint Hnt(int n) {if (n 1)return 1;return 2*Hnt(n - 1) 1; } int main() {int n;scanf(%d, n);int tHnt(n);printf(%d, t); } 结语以上就是有关函数递归的内容希望有所帮助。