C语言-递归和迭代-CSDN博客

 

 write in front
大家好我是Aileen.希望你看完之后能对你有所帮助不足请指正共同学习交流.
本文由Aileen_0v0 原创 CSDN首发 如需转载还请通知⚠️
个人主页Aileen_0v0—CSDN博客
欢迎各位→点赞 + 收藏⭐️ + 留言​
系列专栏Aileen_0v0的C语言学习系列专栏——CSDN博客
我的格言:"没有罗马,那就自己创造罗马~" 

目录

递归概念

递归的思想

递归的限制条件

例子

1.求阶乘

 2.按顺序打印

递归与迭代

例子

1.求第n个斐波那契数

​编辑 利用递归求

利用迭代求

Summary

预告

1.汉诺塔问题

2.青蛙跳台阶问题 

---

本节概要

递归概念

递归:函数自己调用自己

控制台运行结果:

 

递归的思想

把一个大型问题层层转换成一个与原问题相似,但规模较小的子问题求解;直到子问题不能再被拆分,递归就结束了.--- 大事化小

递归的 递是递推的意思  归是回归的意思 

---

递归的限制条件

例子

1.求阶乘

不考虑栈溢出,所以n不能太大,n的阶乘就是 1-n 的数字累乘

int Fact(int n)
{
	if (n <= 0)
		return 1;
	else
		return n * Fact(n - 1);
}

int main()
{
	int n = 0;
	scanf("%d", &n);
	int ret = Fact(n);
	printf("%d\n", ret);
	return 0;
}

求阶乘的过程图解(以3为例),红色表示递退过程,绿色表示回归过程. 

 2.按顺序打印

1.Print( 1234 )

2.==>Print( 123 )                        + printf ( 4 )

3.==>Print( 12 )                + printf ( 3 )

4.==>Print( 1 )        + printf ( 2 )

5.==> printf ( 1 )

画图推演:

 

//按顺序打印
void Print(int n)
{
	if (n > 9)
		Print(n / 10);
	printf("%d ", n % 10);
}


int main() 
{
	int n = 0;
	scanf("%d", &n); //1234
	Print(n);
	return 0;

}

运行结果:

 

在 C 语言中如果被除数和除数都是整数则使用除号 / 进行运算时结果将被截断为整数不会有小数部分。如果被除数和除数中至少有一个是浮点数则使用除号 / 进行运算时结果将保留小数部分。例如

int a = 5, b = 2;
float c = 5.0, d = 2.0;

int result1 = a / b;    // 结果为 2
float result2 = a / b;  // 结果为 2.0
float result3 = c / d;  // 结果为 2.5

在第一个例子中因为被除数和除数都是整数所以结果被截断为整数 2。而在第二个例子中虽然使用的是整数变量但因为将运算结果存储在浮点数变量中所以结果被转换为浮点数 2.0。在第三个例子中被除数和除数都是浮点数所以结果保留小数部分为浮点数 2.5。

---

递归与迭代

虽然递归很好用,但是如果递归深度太深可能会发生栈溢出的问题.

这是刚刚打印,1234的例子,我们通过函数内存中的栈区去观察,它是如何进行打印的,当执行完所有函数以后我们会发现栈区里会给每一个执行完的函数开辟一个空间,直到函数执行完以后,这些空间才会被一个一个的释放出来.

如果这个打印数字很大,比如说 n = 10000 栈的内存没有那么大,就会导致在后面继续开辟内存空间的时候,栈区没有足够的空间提供给函数进行栈帧开辟,就会发生栈溢出(stack over flow)的现象

void test(int n)
{
	if (n <= 10000)
	{
		printf("%d\n", n);
		test(n + 1);
	}
}
int main()
{
	test(1);
	return 0;
}

递归层次过深,发生栈溢出现象 

迭代: 表示一种重复做的事情,循环是一种迭代

我们可以通过迭代(循环)解决阶乘问题

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

运行结果:

例子

1.求第n个斐波那契数

斐波那契数列: 1 1 2 3 5 8 13 21 34 55

 利用递归求

//求第n个斐波那契数
int Fib(int n)
{
	if (n <= 2)
		return 1;
	else
		return Fib(n - 1) + Fib(n - 2);
}

int main()
{
	int n = 0;
	scanf("%d", &n);
	int ret = Fib(n);
	printf("%d\n", ret);
	return 0;
}

运行结果: 

 

//求第n个斐波那契数
int count = 0;
int Fib(int n)
{
	if (n == 3)
		count++;
	if (n <= 2)
		return 1;
	else
		return Fib(n - 1) + Fib(n - 2);
}

int main()
{
	int n = 0;
	scanf("%d", &n);
	int ret = Fib(n);
	printf("%d\n", ret);
	printf("count = %d\n", count);
	return 0;
}

 

---

利用迭代求

int Fib(int n)
{
	int a = 1;
	int b = 1;
	int c = 1;
	while (n > 2)
	{
		c = a + b;
		a = b;
		b = c;
		n--;
	}
	return c;
}

int main()
{
	int n = 0;
	scanf("%d", &n);
	int ret = Fib(n);
	printf("%d\n", ret);
	//printf("count = %d\n", count);
	return 0;
}

运行结果:

Summary

1.如果一个问题使用 递归方法 写代码, 是非常方便的,简单的

    写出的代码是没有明显缺陷的,这时候使用递归即可

2.如果使用递归写的代码,是存在明显缺陷的

比如:栈溢出,效率低下等

这时候必须考虑其他方式,比如: 迭代 

预告

1.汉诺塔问题

 相传在古印度圣庙中有一种被称为汉诺塔的游戏。该游戏是在一块铜板装置上有三根杆(编号A、B、C)在A杆自下而上、由大到小按顺序放置64个金盘。                        ​​​​​​​        ​​​​​​​        ​​​​​​​ 游戏的目标把A杆上的金盘全部移到C杆上并仍保持原有顺序叠好。操作规则每次只能移动一个盘子并且在移动过程中三根杆上都始终保持大盘在下小盘在上操作过程中盘子可以置于A、B、C任一杆上。

2.青蛙跳台阶问题 

有一只青蛙一次可以跳一个台阶也可跳2个台阶如果有n个台阶这只青蛙有多少种跳法跳上n个台阶