网站如何做背景音乐,WordPress设置用户访问个数,银川市建设诚信平台网站,百度首页推广递归其实是⼀种解决问题的方法#xff0c;在C语言中#xff0c;递归就是函数自己调用自己。
一、递归的介绍
1.1递归的思想
把⼀个大型复杂问题层层转化为⼀个与原问题相似#xff0c;但规模较小的子问题来求解#xff1b;直到子问题不能再被拆分#xff0c;递归就结束…递归其实是⼀种解决问题的方法在C语言中递归就是函数自己调用自己。
一、递归的介绍
1.1递归的思想
把⼀个大型复杂问题层层转化为⼀个与原问题相似但规模较小的子问题来求解直到子问题不能再被拆分递归就结束了。所以递归的思考方式就是把大事化小的过程。递归中的递就是递推的意思归就是回归的意思。
1.2 递归的限制条件
递归在书写的时候有2个必要条件 • 递归存在限制条件当满足这个限制条件的时候递归便不再继续。 • 每次递归调用之后越来越接近这个限制条件。
二、递归的例子
2.1求解n的阶乘 ⼀个正整数的阶乘factorial是所有小于及等于该数的正整数的积并且0的阶乘为1。自然数n的阶乘写作 n!。 通过分析可以发现n的阶乘公式n n ∗ (n − 1)! 实现如下
int Fact(int n)
{if(n 0)return 1;elsereturn n * Fact (n - 1);
}这里的n不宜过大否则会造成栈溢出。
2.2 顺序打印数字的每一位 输⼊⼀个整数m打印这个按照顺序打印整数的每⼀位。 比如 输⼊1234 输出1 2 3 4 输⼊520 输出5 2 0 如果n是⼀位数n的每⼀位就是自己n是超过1位数的话就得拆分每⼀位。 实现如下
void Print(int n)
{if(n9){Print(n/10);}printf(%d , n%10);
}2.3斐波那契数列 代码实现
int Fib(int n)
{if(n2)return 1;elsereturn Fib(n-1)Fib(n-2);
}三、迭代与递归
在C语言中每⼀次函数调都要需要为本次函数调用在栈区申请⼀块内存空间来保存函数调用期间的各种局部变量的值这块空间被称为运行时堆栈或者函数栈帧。 函数不返回函数对应的栈帧空间就⼀直占用所以如果函数调用中存在递归调用的话每⼀次递归函数调用都会开辟属于自己的栈帧空间直到函数递归不再继续开始回归才逐层释放栈帧空间。所以如果采用函数递归的方式完成代码递归层次太深就会浪费太多的栈帧空间也可能引起栈溢出stack overflow的问题。 这一部分的具体内容会在下一篇博客中讲述。
上述分析表明在一般情况下迭代效率远高于递归。
例如上面的2.3输入50这样的数字时需要很长时间才能拿到我们想要的结果因此优化了该代码
int Fib(int n)
{int a 1;int b 1;int c 1;while(n2){c ab;a b;b c;n--;}return c;
}
