【C语言】带你玩转递归，迭代算法 |
您所在的位置：网站首页 › 迭代过程是什么意思 › 【C语言】带你玩转递归，迭代算法 |
【C语言】带你玩转递归，迭代算法
|
勤时当勉励 岁月不待人 C/C++ 游戏开发 Hello，这里是君兮_，今天给大家带来一篇函数递归的文章，它在我们以后的数据结构中也非常重要。 递归算法与迭代算法 前言一.什么是递归？二.递归的两个必要条件三.配合实例讲解打印整型数据的每一位画图解释循环实现 求字符串长度循环实现 四.递归与迭代斐波那契数列1.递归求解递归算法的不足 2.使用迭代算法改进我们的代码 五.扫雷游戏中的递归总结 前言不像加减乘除，我们求学期间就已经见识过多次了，而大多数初学者在此之前可能都从未了解接触过递归思想，这使得很难上手递归算法，今天我希望能尽我所能结合画图已经例题的方法把递归算法讲解的通俗易懂，帮助大家入门 废话不多说了，我们开始今天的内容 一.什么是递归？ 程序调用自身的编程技巧称为递归（ recursion）。递归做为一种算法在程序设计语言中广泛应用。 递归算法通常指一个过程或函数在其定义或说明中直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。(也就是说我们现在学的需要使用递归的场景大多数通过循环也能解决，在下面介绍的例子中会用循环也实现一遍) 递归的主要思考方式在于：把大事化小 当你在使用递归时遇到思考瓶颈，请牢记大事化小的思想！！ 二.递归的两个必要条件 1.存在限制条件，当满足这个限制条件的时候，递归便不再继续。2.每次递归调用之后越来越接近这个限制条件。 当你不满足这两个条件的任意一条时，程序会陷入死循环当你的递归写出bug时，往往是没考虑上面这两个条件或者条件设置有误，调试时多想想递归条件最好能够画下图帮助自己理解。 三.配合实例讲解 打印整型数据的每一位实例一： 接受一个整型值（无符号），按照顺序打印它的每一位。 例如： 输入：1234，输出 1 2 3 4 代码如下： #include void print(int n) { if(n>9)//如果不大于9直接打印当前n的值即可 { print(n/10); } printf("%d ", n%10); } int main() { int num = 1234; print(num); return 0; } 我们想要把一个四位数甚至更多位的数每一位给剥离出来，首先要想到的是怎么得到每一位我们知道，对10取余%就可以得到这个数的个位的数，而除以10就可以把这一位给消去，此时我们就可以这样实现(以下把n当作一个四位数举例)先让n对10%得到此时这一位的数，然后将n/10来到下一位，再让n对10%得到这位数继续朝下进行直至n对10%等于0，说明此时n是个小于10的数只剩下它需要取了，取下它结束递归即可 画图解释 递归的递就是传递的意思，而归的意思是回归 这就是递归！解释完了递归在这段代码的应用，我们来讲讲这个代码中出现的问题当我们中用户某天突发奇想输入了一个负数进去会发生什么呢？  我们这个程序设定的条件是只针对正数的，要想输入一个负数也能打印就得这样修改代码
void print(int n)
{
if (n > 9)//如果不大于9直接打印当前n的值即可
{
print(n / 10);
}
else if (n
int num = -1234;
print(num);
return 0;
}
或者把我们传入的int改为一个无符号整型 void print(unsigned int n) { if (n > 9)//如果不大于9直接打印当前n的值即可 { print(n / 10); } /*else if (n < -9) { print(n / 10); }*/ printf("%d ", n % 10); } 这里虽然都是非常简单的地方，但我想提醒大家的是，无论在递归或者任何其他程序的编写中我们都得尽可能考虑各方面的情况，在以后的程序猿工作中，我们要知道用户是不总是照着你的指示来使用程序的，我们得尽可能保证程序的避免上面这种bug。 循环实现 //判断输入数字位数 #include int Strlen(unsigned int n) { int count = 0; while (n / 10) { count++; n /= 10; } return count; } void print(unsigned int n) { int i = 0; int ret = Strlen(n); if (n > 9) { for (i = ret; i > 0; i--) { int m = pow(10, i); printf("%d ", n / m); n %= m; } } printf("%d", n); } int main() { int num = 123456789; print(num); return 0; }我们先来看看效果 说实话，同样实现一个功能递归比循环简单多了，从代码的行数就能看出来。这就是我们使用递归算法的意义 求字符串长度实例二 编写函数不允许创建临时变量，求字符串的长度。 #include int Strlen(const char*str) { if(*str == '\0')//是个空字符串 return 0; else return 1+Strlen(str+1);//每次递归让Strlen朝后移动一位直至遇到"\0"不满足递归条件 } int main() { char *p = "abcde"; int len = Strlen(p); printf("%d\n", len); return 0; } 咱们还是画个图理解吧
求第n个斐波那契数(不考虑栈溢出) 1 1 2 3 5 8 13 21 34 55 … 每前2个的数的和是第三个数，我们把拥有这种性质的数列称为斐波那契数列。 //求第n个斐波那契数 //1 1 2 3 5 8 13 21 34 55 ... int fib(int n) { if (n if (n == 3) count++; if (n int result; int j; int i; result = j = 1; while (n > 2) { n -= 1; //实现每一次n减小时新的n-1与n-2并赋值给n i = j;//把n-1的值给n-2 j = result;//把此时n的值给n-1 result = i + j;//n的值等于此时的(n-1)+(n-2) } return result; } int main() { int n = 0; scanf("%d", &n); int ret = fib(n); printf("%d\n ", ret); }看看现在的结果 这里由于int型能存放的数不够肯定栈溢出了，但是先别管结果对不对，你就说快不快吧，是不是能给你个结果？这意味着咱们把代码重复冗杂的问题解决了！ 这里还有几个经典的问题比如汉诺塔和青蛙跳台阶，后面都会有具体博客去讲的。 五.扫雷游戏中的递归 另外，在改进扫雷游戏中我们也使用了递归算法，但是那个比较复杂，我也在扫雷游戏那篇博客里具体讲了，感兴趣的可以去看看，链接就放在这里啦！ 【C语言】万字教学，带你分步实现扫雷游戏(内含递归函数解析)，剑指扫雷，一篇足矣 总结 以上就是今天的所有内容了，今天我们具体分析的递归算法和迭代算法，同时对比了他们之间的区别与优缺点。如果你有任何疑问欢迎在评论区指出或者私信我，我看到后会第一时间回复的哦！新人博主创作不易，如果感觉文章内容对你有所帮助的话不妨三连一下这个新人博主再走呗。你们的支持就是我更新的动力！！！ （可莉请求你们三连支持一下博主！！！点击下方评论点赞收藏帮帮可莉吧） |
提示： 1. 许多问题是以递归的形式进行解释的，这只是因为它比非递归的形式更为清晰。 2. 但是这些问题的迭代实现往往比递归实现效率更高，虽然代码的可读性稍微差些。 3. 当一个问题相当复杂，难以用迭代实现时，此时递归实现的简洁性便可以补偿它所带来的运行时开销
【本文地址】