重庆网站seo搜索引擎优化,做网站接广告,网站的用户登录一般怎么做的,自己怎么做网站卖车文章目录 1.递归是什么#xff1f;2.递归的限制条件3.递归举例3.1 举例1#xff1a;求n的阶乘3.1.1 分析和代码实现 3.2 举例2#xff1a;顺序打印一个整数的每一位3.2.1 分析和代码实现 4.递归与迭代举例3#xff1a;求第n个斐波拉切数 1.递归是什么#xff1f;
递归是学… 文章目录 1.递归是什么2.递归的限制条件3.递归举例3.1 举例1求n的阶乘3.1.1 分析和代码实现 3.2 举例2顺序打印一个整数的每一位3.2.1 分析和代码实现 4.递归与迭代举例3求第n个斐波拉切数 1.递归是什么
递归是学习C语言函数绕不开的话题那什么事递归呢?
递归其实是一种解决问题的方法在C语言中递归函数就是自己调用自己。
写一个史上最简单的C语言递归代码
#include stdio.h
int main()
{printf(hehe\n);main();//main函数中又调用了main函数return 0;
}上述就是一个简单的递归程序,只不过上面的递归只是为了演示递归的基本形式不是为了解决问题代码最终也会陷入死递归导致栈溢出。具体如下图所示 递归的思想
把一个大型复杂问题层层转化为一个与原问题相似但规模较小的子问题来求解直到子问题不能再被拆分那么递归就结束了所以递归的思考方式就是大事化小的过程。
递归中的递就是递推的意思归就是回归的意思。
2.递归的限制条件
递归在书写的时候有2个必要条件
递归存在限制条件当满足这个限制条件的时候递归便不再继续。每次递归调用之后会越来越接近这个限制条件。
好了接下来博主将举几个例子让大家逐步体会这两个限制条件。
3.递归举例
3.1 举例1求n的阶乘
计算n的阶乘不考虑溢出,n的阶乘就是1~n的数字累积相乘。
3.1.1 分析和代码实现
我们知道n的阶乘公式n!n*(n-1)!
举例
5! 5*4*3*2*1
4! 4*3*2*1
所以:5! 5*4!这样的思路就是把一个较大的问题转换为一个与原问题相似但规模较小的问题来求解的。
n!----n*(n-1)!
(n-1)!------(n-1)*(n-2)!
…
直到n是1或者0时不在拆解
再稍微分析一下当n1的时候n的阶乘1.其余n的阶乘都是可以通过上述公式计算。n的阶乘的递归公式如下 那我们就可以写出函数Fact求n的阶乘假设Fact(n)就是求n的阶乘那么Fact(n)就是求n的阶乘那么Fact(n-1)就是n-1的阶乘 函数如下代码所示
int Fact(int n)
{
if(n0)return 1;
elsereturn n*Fact(n-1);
}int main()
{int n 0;scanf(%d, n);int ret Fact(n);printf(%d\n, ret);return 0;
}运行代码结果如下所示 除此之外这个n的阶乘函数的递推和回归如下图所示 从这幅图可以得知当n0时,Fact(0)1,Fact(1)1*Fact(0)1然后逐一向上层回归因此我们就能求得出Fact(5)120。
3.2 举例2顺序打印一个整数的每一位
输入一个整数m,打印这个按照顺序打印整数的每一位。
比如 输入1234 输出1 2 3 4 输入530 输出530 3.2.1 分析和代码实现
这个题目如果放在我们面前首先想到的是怎么得到这个数的每一位呢
如果n是一位数n的每一位就是n自己。
n是超过1位数的话就得拆分每一位 1234%10就能得到4然后1234/10得到123这就相当于去掉了4 然后继续对123%10就得到了3再除10去掉3以此类推 不断的%10 和\10 操作直到1234的每一位都得到 但是这里有个问题就是得到的数字顺序是倒着的 但是我们有了灵感我们发现一个数字的最低位是最容易的得到的通过%10就能得到那我们假设想写一个函数Print来打印n的每一位如下图表示 我们就以此类推下去就有
Print(1234)
Print(123) printf(4)
Print(12) printf(3)
Print(1) printf(2)
printf(1)直到被打印的数字变成1位数的时候就不需要拆分递归结束。
那么代码完成也就比较清楚
void Print(int n){if(n9){Print(n/10)}printf(%d ,n%10);
}int main(){int n0;scanf(%d,n);Print(n);return 0;
}我们来看一下代码的输入和输出结果 在这个解题的过程中我们就是使用了大事化小的思路
把Print(1234)打印1234每一位拆解为首先Print(123)打印123的每一位再打印得到的4
把Print(123)打印123每一位拆解为首先Print(12)打印12的每一位再打印得到的3
把Print(12)打印12每一位拆解为首先Print(1)打印1的每一位再打印得到的2
直至Print打印的是一位数直接打印就行。
下面是递推和回归的流程图大家可以看一下~ 由图我们得知当用户输入1234时进入Print函数内部会层层递推下去直到递推到Print(1)19,则打印出1出来接着用层层回归上去直到把1234的每一位都打印出来递归就结束然后就会返回到main函数内部继续执行接下来的语句。
4.递归与迭代
递归是一种很好的编程技巧但是和很多技巧一样也是可能会被误用的就像举例一样看到推导的公式很容易就会写成递归的形式 int Fact(int n)
{if(n0)return 1;elsereturn n*Fact(n-1);
}事实上虽然Fact函数是可以产生正确的结果但是在递归函数调用的过程中涉及一些运行时的开销。 在C语言中每一次函数调用都要需要为本次函数调用在栈区申请一块内存空间来保存函数调用期间 的各种局部变量的值这块空间被称为运行时堆栈或者函数栈帧。 函数不返回函数对应的栈帧空间就一直占用所以如果函数调用中存在递归调用的话每一次递归 函数调用都会开辟属于自己的栈帧空间直到函数递归不再继续开始回归才逐层释放栈帧空间。 所以如果采用函数递归的方式完成代码递归层次太深就会浪费太多的栈帧空间也可能引起栈溢 出stack over flow的问题。 所以如果我们不想使用递归就得想想其他的办法通常就是迭代的方式(迭代指的是循环的方式)
比如我们计算n的阶乘也可以是1~n的数字累成在一起的因此我们的代码可以写成这样
int sum(int n) {int ret 1;for (int i 1; i n; i)ret * i;return ret;
}int main() {int n 0;scanf(%d, n);printf(%d, sum(n));return 0;
}上述代码是能够完成任务并且效率是比递归的方式更好的。
事实上我们看到的许多问题是以递归的形式进行解释道这只是因为它比非递归的方式更加清晰但是这些问题的实现迭代实现往往比递归实现效率更高。
当一个问题非常复杂难以使用迭代的方式实现此时递归实现的简洁性便可以补偿它所带来的运行时的开销。
举例3求第n个斐波拉切数
我们也能举出更加极端的例子就像计算第n个斐波那契数是不适合使用递归求解的但是斐波那契 数的问题通过是使用递归的形式描述的。如下图所示 当我们看到这个公式很容易诱导我们将代码写成递归的形式具体代码如下所示
int Fib(int n)
{
if(n2)return 1;
elsereturn Fib(n-1)Fib(n-2);
}主函数代码所示
#include stdio.h
int main(){int n0;scanf(%d,n);int retFib(n);printf(%d\n,ret);return 0;
}但是当我们n输入为50的时候需要花很长时间才能算出结果这个计算所花费的时间是我们很难接受的这也说明递归的写法是非常低效的这是为什么呢 其实当递归程序不断的展开在展开的过程中我们就很容易发现在递归的过程中会有很多重复计算而且递归层次越深冗余计算就会越多我们可以用代码来测试一下
#include stdio.h
int count 0;int Fib(int n) {if (n 3)count;if (n 1 || n2) {return 1;}elsereturn Fib(n - 1) Fib(n - 2);
}int main() {int n 0;scanf(%d, n);int ret Fib(n);printf(%d, ret);printf(\ncount%d\n, count);return 0;
}输出结果如下所示 从这里我们可以看出在计算第40个斐波拉切数的时候使用递归方式第3个斐波拉切数就被重复计算了39088169次实际上这些计算时非常冗余的。所以斐波拉切数的计算使用递归是非常不明智的选择因此我们就得使用迭代的方式来解决。
我们知道斐波拉切数的前2个数都为1然后前2个数相加就是第3个数从下到大计算就行了。
于是我们就有了下面这行代码
int Fib(int n) {int a 1;int b 1;int c 1;for (int i 3; i n; i) {c a b;a b;b c;}return c;
}int main() {int n 0;scanf(%d,n);int t Fib(n);printf(%d, t);return 0;
}在这行代码中我们首先把变量a,b,c的值赋值为1当用户输入的值n3时会进入循环首先我们把前两个数的和赋给c,接下来再把b的值赋给a,再把c的值赋给b,这样a和b的数字都会随着n的数字的大小而逐渐增大从而我们可以计算出第n个斐波拉切数是多少。
因此我们可以发现迭代的方式去实现这个代码效率就要高出很多了。
有时候递归虽好但是也会引入一些问题所以我们一定不能迷恋递归适可而止就可以了。
好啦今天递归的知识点就讲到这里如果觉得博主讲得还不错的话欢迎一键三连支持一下谢谢
