投稿
程序员

C语言进阶之旅（6）递归vs迭代

作者：admin 2021-09-18 我要评论

递归 温馨提示函数部分中比较难一块需要大量的积累和练习不懂的地方多调试和画图才能有递归的思想 ?????????????? 博主就是不懂就画图画完图就茅塞顿开 文章目录...

（在说正事之前，我要推荐一个福利：你还在原价购买阿里云、腾讯云、华为云服务器吗？那太亏啦！来这里，新购、升级、续费都打折，能够为您省60%的钱呢！2核4G企业级云服务器低至69元/年，点击进去看看吧>>>)

递归

温馨提示：函数部分中比较难一块，需要大量的积累和练习，不懂的地方多调试，和画图，才能有递归的思想！！！！
??????????????博主就是不懂就画图，画完图就茅塞顿开

文章目录

思维导图

在这里插入图片描述?????????看这个思维导图，我大致说一下他的运用场景，和下面的例子比较好理解


?????????递归自己直接或间接调用自己，把一个大型的问题层层转换成一个小的问题，需要的代码也是少之又少，大大减少了代码量，递归思想：大事化小，看例子吧，结合例子比较好懂。

例子思路

下面举的例子没有提到的思路都在这里

例子1

输入123打印 1 2 3
思路

  • 123中谁最好获取，当然是3，123%10就获得3，然后在123/10获得12在%10以此往复，就可以获得，那我们来看看代码吧
    在这里插入图片描述
void print(int n)
{
	if (n >9)
	{
		print(n / 10);//n大于9就进入递归，直到n<9是跳出递归
	}
	printf("%d ", n % 10);
}
int main()
{
	int num = 123;
	print(num);
	return 0;
}

看他的运行图比较好理解
在这里插入图片描述

函数从哪里进来就要从哪里返回回去

例子2

n的阶乘（迭代）

int Fib(int n)
{
	int i = 0;
		int fib = 1;
	for ( i =1; i <=n; i++)
	{
		fib = fib * i;
	}
	return fib;
}
int main()
{
	int n = 0;
	scanf("%d", &n);

	int ret =Fib(n);
	printf("%d", ret);
	return 0;
}

n的阶乘（递归）

int Fib(int n)
{
	if (n <2)
	{
		return 1;
   }
	else
	{
		return n*Fib(n - 1) ;
	}
}
int main()
{
	int n = 0;
	scanf("%d", &n);

	int ret = Fib(n);
	printf("%d", ret);
	return 0;

}
  • 这里和迭代（循环）起来递归更加简单一个if else就搞定了，用少量代码就完成了（好方便哈哈）

递归的流程图
在这里插入图片描述

例子3

模拟实现strlen

  • strlen的作用是就求字符串长度
  • strlen是会记录\0前面字符个数

strlen（迭代版）

int my_strlen(char* a)//传过来地址，也用地址接收
{
	int count = 0;
	while(*a != '\0')
	{
		a++;
		count++;
    }
	return count;
}
int main()
{
	char arr[] = "abcdef";

	printf("%d", my_strlen(arr));//数组的地址就是首元素
	return 0;
}

strlen（递归版）

int my_strlen(char* a)//传过来地址，也用地址接收
{
	if (*a != '\0')
	{
		return 1 + my_strlen(a + 1);//这里不要用a++或者++a,不然会改变a的值假设这不是数组是变量
	}
	else
		return 0;
		
}
int main()
{
	char arr[] = "abcdef";

	printf("%d", my_strlen(arr));//数组的地址就是首元素
	return 0;
}

流程图
在这里插入图片描述

例子 4

斐波那契数列

在这里插入图片描述

规律就是，前面俩数向加得出后面那个数

  • 斐波那契就是n=（n-1）+（n-2）

递归版


int Fib(int n)
{
	if (n <= 2)//斐波那契数列前俩位是1 1
	{
		return 1;
	}
	else
	{
		return Fib(n - 1) + Fib(n - 2);
	}
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	printf("%d",Fib(n));
	return 0;
}

看一下流程图

在这里插入图片描述

迭代版

int Fib(n)
{
	int a = 1;
	int b = 1;
	int c = 1;
	if (n <= 2)
	{
		return c;//斐波那契前面俩数是 
	}
	while (n > 2)
	{
		c = a + b;
		a = b;
		b = c;
		n--;
	}
	return c;	
}

int main()
{
	int n = 0;
	scanf("%d", &n);
	printf("%d", Fib(n));
	return 0;
}
  • 这里看起来比起来还是比递归麻烦呀，又是判断，又是循环，又是交换，麻烦死了还不如写递归呢，直接一个判断，写个一个条件就开始递归多方便，不不不，那我们看一下下面的例子，求第50个斐波那契数的时间

是不是以为程序挂了，不不不，其实计算机在很努力的在算，不信我给你看
在这里插入图片描述

????????????????????????????????????????????骗你是小狗
在这里插入图片描述
………………………………喝了一杯水，还没好，又是一杯，还没好，煎熬
………………………………，哦出来了花了6分43秒
在这里插入图片描述
为啥递归要花怎么长时间呢，应为他的效率低

因为他假设要找第50，他就要找的第49 和48然后就要，然后找49就要找到48和47………………，找一位数就进行了多次重复大量的计算，算出这个数大致算了2^n-1次方在这里插入图片描述

  • 这里迭代就很快，ctrl+f5调试，直接给出答案

例子 5

  • 字符串逆序
  • 字符数组中“abcdef”,交换位置,“fedcba”
    思路
    1:加换a和f，在b和e,这个不是和二分查找原因二分查找思想 二分查找的思路

迭代版 1

#include<string.h>
void reverse_string(char* a,int s)//传过来是地址就用地址接收
{
	int left = 0;
	int  right = s - 1;
	while(left<right)
	{
		char cmp = *(a + left);//=str[left]
		*(a + left) = *(a + right);
		*(a + right) = cmp;

		left++;
		right--;
	}
}

int main()
{
	char arr[] = "abcdef";
	int st = strlen(arr);
	reverse_string(arr,st);//数组的地址就是首元素
	printf("%s", arr);
	return 0;

}

迭代版 2

#include<string.h>
void reverse_string(char* a, int s)//传过来是地址就用地址接收
{
	int left = 0;
	int  right = s - 1;
	while (left < right)
	{
		char cmp = a[left];//=str[left]
	    a[left] = a[right];
		a[right] = cmp;
		left++;
		right--;
	}
}

int main()
{
	char arr[] = "abcdef";
	int st = strlen(arr);
	reverse_string(arr, st);//数组的地址就是首元素
	printf("%s", arr);
	return 0;
}

递归版
在这里插入图片描述
??????????????这里想到递归的思路很难，谁能想到，吧后面给换成\0,然后在字符串长度对比天呐！！

void reverse_strling(char* str)
{
	char tmp = *str;
	int len = strlen(str);
	*str = *(str + len - 1);
	*(str + len - 1) = '\0';

	if (strlen(str + 1) >= 2)
	{
		reverse_strling(str + 1);
	}
	*(str + len - 1) = tmp;
}
int main()
{
	char arr[] = "abcdef";
	reverse_strling(arr);//数组的地址就是首元素
	printf("%s", arr);
	return 0;
}

流程图
在这里插入图片描述

这里总结得出，递归与跌代，不向上下，各有各的好处，作为裁判的我（公平公正）平局

拓展

栈（现在所认识到的）

  • 函数在自己调用自己的时候会在栈区中创建一块新的空间，栈溢出就是把栈撑满了
    在这里插入图片描述

这个就是内存情况
在这里插入图片描述

注意事项

  1. 写递归的时候一定要有判断条件，和逼近跳出递归的条件
  2. 递归不要太深，太深容易栈溢出（strank）
  3. 如果递归效率慢，那么就不适合递归，那就一定要写出迭代方法（不管多麻烦），递归的目的是大事化小，如果效率慢，岂不是本末倒置了
  4. 创建函数的时，取名字最好和他的功能对应，不要随便取

青蛙跳台阶

正常跳台阶：一只青蛙一次可以跳上1级台阶，也可以跳上2级，也可以跳上3级。
求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

  • 设跳1级---->跳法1------->[1]
  • 跳2级----->跳法2----->[1,1],[2]
  • 跳3级---->跳法3----->[1,1,1],[2,1],[1,2],
  • 跳4级----->跳法5---->[1,1,1,1],[2,2],[1,1,2,2],[2,2,1,1] [1,2,1]
  • 跳5级----->跳法8---->[1,1,1,1,1],[2,2,1],[1,2,2],[2,1,2,],[[2,1,1,1,1],[1,2,1,1],[1,1,2,1,1]，[1,1,1,2],

不能说一样，就是一毛一样
在这里插入图片描述

汉诺塔

汉诺塔（Tower of Hanoi），又称河内塔，是一个源于印度古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
在这里插入图片描述

A=1,2,3. B =0. C= 0

  1. A(1)–>C
  2. A(2)—>B
  3. C(1)---->B(2)
  4. A(3)---->C
  5. B(1)---->A
  6. B(2)—>C(3)
  7. A(1)---->C(2)

青蛙跳台阶和汉诺塔，会在下期更新…………
（如果有错误记得联系博主（QQ：1696912943），或者直接在评论区提出，私信，博主会及时进行改正，谢谢）
持续更新中………………

；原文链接：https://blog.csdn.net/Legwhite/article/details/115921142

版权声明：本文转载自网络，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。本站转载出于传播更多优秀技术知识之目的，如有侵权请联系QQ/微信：153890879删除

相关文章
  • C语言进阶之旅（6）递归vs迭代

    C语言进阶之旅（6）递归vs迭代

  • 大学四年，学了这些计算机基础知识，成

    大学四年，学了这些计算机基础知识，成

  • 聊聊我是如何编程入门的

    聊聊我是如何编程入门的

  • 这样学编程，直接原地起飞啊！

    这样学编程，直接原地起飞啊！

腾讯云代理商
精彩导读
/images/defaultpic.gif

element中Steps步骤条和Tabs标签页关联

/images/defaultpic.gif

2021 年云原生技术发展现状及未来趋势

/images/defaultpic.gif

HaaS EDU场景式应用学习 - 贪吃蛇

/images/defaultpic.gif

JavaScript实现链表插入排序和链表归并

/images/defaultpic.gif

知其然更要知其所以然，聊聊SQLite软件

/images/defaultpic.gif

大数据时代下的新宠：是时候熟悉NoSQL

海外云服务器
热门资讯
备案：湘ICP备15009499号-1
网站简介 投稿须知 商务合作 版权申明 技术支持：TOP云