C语言之函数递归篇_c语言递归专项

目录

什么是递归？

递归的条件

练习NO1.

Point1.用while

Point2.用a=a/10

根本原因 

练习NO2.

Point1.str++和++str和str+1

递归与迭代（循环）

练习NO1.

练习NO2.

总结

思考经典问题

---

什么是递归？

程序调用自身的编程技巧称为递归（recursion）。

递归作为一种算法在程序设计语言中广泛应用。

一个过程或函数在其定义或说明中有直接或间接调用自身的一种方式。

它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复的计算，大大地减少了程序地代码量。递归的主要思考方式在于：把大事化小

最简单的递归，那为什么它是错误的❌？？ 

//最简单的错误递归
#include<stdio.h>
int main()
{
	printf("haha\n");
	main();
	return 0;
}

 

 因为它没有限制条件。

递归的条件

1.存在限制条件，当满足这个限制条件的时候，递归便不在继续。

2.每次递归调用之后越来越接近这个限制条件。

练习NO1.

//接受一个整型值（无符号），按照顺序打印它的每一位。 
//例如： 输入：1234，输出 1 2 3 4.

按照我们传统方式：

//传统方式
#include<stdio.h>
int main()
{
	//1234%10=4
	//1234/10=123
	//依次取模和除法
	int a = 0;
	int num = 0;
	scanf("%d", &a);
	while (a)//a除以到最后1/10得0.1不是整数表达式，跳出循环
	{
		num = a % 10;
		printf("%d ", num);
		a = a / 10;
		
	}
	return 0;
}

我们今天学习到递归，我们就用递归得逻辑实现这个问题。（函数自己调用自己实现递归逻辑） 

//递归逻辑
//Print能将参数得num得每一位打印在屏幕上
//Print（1234）
//Print(123) +4
//Print(12)+3+4
//Print(1)+2+3+4

#include<stdio.h>
void Print(int a)//1234
{
	if(a > 9)//a是两位数，当a是一位数时跳出循环
	
	{
		Print(a/10);
	}
    printf("%d ", a%10);
}
int main()
{
	int a = 0;
	scanf("%d", &a);
	Print(a);
	return 0;
}

 讲解如下：

理解到程序到底是怎样执行的。

变量a是怎样改变的。

递归：递进 回归。 

Point1.用while

#include<stdio.h>
void Print(int a)//1234
{
	while(a > 9)
	{
		Print(a / 10);
	}
	printf("%d ", a % 10);
}
int main()
{
	int a = 0;
	scanf("%d", &a);
	Print(a);
	return 0;
}

所以即使加了限制条件的递归也不一定是正确的，但不加限制条件绝对是错误的❌。

必要条件必须要有，有不一定对，没有一定错。❌

循环和分支使用适合。

Point2.用a=a/10

#include<stdio.h>
void Print(int a)//123
{
	if(a > 9)
	{
		a = a / 10;
		Print(a);
	}
    printf("%d ", a%10);
}
int main()
{
	int a = 0;
	scanf("%d", &a);
	Print(a);
	return 0;
}

 

 所以尽量直接写，不要用赋值去改变某个变量。

根本原因 

函数之所以能实现，能实现递归。

都是因为，函数在调用的时候会维护一个函数栈帧（内存上的一块区域）。

函数调用开始，函数栈帧创建，函数调用结束后，栈帧销毁。

关于函数栈帧创建和销毁，后面会详细介绍。✔✔✔✔

练习NO2.

//编写函数不允许创建临时变量，求字符串的长度。

求字符串长度strlen和sizeof 

#include<stdio.h>
int main()
{
	char arr[] = "abc";
	size_t str = strlen(arr);
	printf("%zd", str);
	return 0;
}

size_t 是一种类型，是无符号整型的。

size_t 就是为sizeof设计的

size_t l类型的数据打印的时候使用%zd

strlen包含头文件#include<string.h>

strlen只计算\0之前的字符个数。

sizeof计算\0。

让我们编写函数求字符串长度，也就是模拟strlen的功能（传统方式）。

arr指的是字符串首元素的地址
指针变量str来接受
*str指的是元素
str指的是地址
str++可以让地址往后移动
count计算
*str依次跟着往后移动
直到*str == '\0'就停止循环
返回count计算元素的个数

size_t my_strlen(char* str)//把数组第一个字符地址传过去
{
	int count = 0;
	while (*str != '\0')
	{
		str++;
		count++;
	}
	return count;
}
#include<stdio.h>
int main()
{
	char arr[] = "abc";
	size_t str=my_strlen(arr);//编写函数求字符串长度
	printf("%zd", str);
	return 0;
}

函数递归的思想：大事化小来解决问题呢！

递归求字符串长度
//my_strlen("abc");
//1+my_strlen("bc");
//1+1+my_strlen("c");
//1+1+1+my_strlen("\0");
//1+1+1+0=3

size_t my_strlen(char* str)//把数组第一个字符地址传过去
{
	if (*str == '\0')
		return 0;
	else
		return 1 + my_strlen(str + 1);
}
#include<stdio.h>
int main()
{
	char arr[] = "abc";
	size_t str = my_strlen(arr);//编写函数求字符串长度
	printf("%zd", str);
	return 0;
}

讲解如下： 

Point1.str++和++str和str+1

str++：

++str ：

 str++是先使用了my_strlen函数在+1

++str是先+11再使用my_strlen函数

最好还是使用str+1，++在其他情况下可能会改变str的前后的值，有副作用。

递归与迭代（循环）

练习NO1.

//求n的阶乘。（不考虑溢出）

#include<stdio.h>
int Fac(int i)
{
	if (i <= 1)
		return 1;
	else
		return i * Fac(i - 1);
}
int main()
{
	int i = 0;
	scanf("%d", &i);
	int ret = Fac(i);
	printf("%d\n", ret);
	return 0;
}

 

根据数学公式，我们可以轻松的用函数递归写出代码，可是我们发现，当我们输入的值过大得不到我们想要的结果，这是为什么呢？

第一种情况：int所能容纳的范围有限，超出了int容纳的范围哦。

第二种情况：栈溢出。参数比较大，报错：stack overflow。系统分配给程序的栈空间是有限的，但是如果出现了死循环，或者（死递归），这样有可能导致一直开辟栈空间，最终产生栈空间耗尽的情况，这种现象我们称为栈溢出。（栈空间大小我们可以修改）。

那我们应该怎样去解决栈溢出的问题呢？把函数递归转化成函数迭代（循环）来实现题目要求

#include<stdio.h>
int Fac(int i)
{
	int j = 0;
	int r = 1;
	for (j = 1; j <= i; j++)
	{
		r = r * j;
	}
	return r;
}
int main()
{
	int i = 0;
	scanf("%d", &i);
	int ret = Fac(i);
	printf("%d\n", ret);
	return 0;
}

//错误点❌
int Fac(int i)
{
	int j = 0;
	for (j = 1; j < i; j++)//i会变
	{
		i = i * j;
	}
	return i;
}
//i会改变不能实现阶乘
//所以不要把输入值当作变量去使用
//输入值是循环限制条件即可

我们解决了栈溢出的问题，但超出int所容纳范围的问题都存在！ 

练习NO2.

//求第n个斐波那契数。（不考虑溢出）
斐波那契数列（Fibonacci sequence），又称黄金分割数列，
因数学家莱昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，
故又称“兔子数列”，其数值为：1、1、2、3、5、8、13、21、34……在数学上，（前两个数相加等于第三个数）
这一数列以如下递推的方法定义：F(0)=1，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）。

#include<stdio.h>
int Fib(int n)
{
	if (n <= 2)
		return 1;
	else
		return Fib(n - 2) + Fib(n - 1);
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	int ret = Fib(n);
	printf("%d", ret);
	return 0;
}

 

 但是当数字过大，例如50，计算一直在持续，效率很低，为什么呢？

 因为有大量重复的计算。

 尽管计算效率很差，但是为什么没有溢出。因为一边递推一边回归，所以栈一边创建一边销毁。

接下来我们还是采用迭代（循环）来解决效率问题

#include<stdio.h>
int Fib(int n)
{
	int a = 1;
	int b = 1;
	int c = 1;//n<=2 c等于1
	while (n > 2)
	{
		c = a + b;
		a = b;
		b = c;
		n--;//循环n-2次相当于相加的次数
	}
	return c;
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	int ret = Fib(n);
	printf("%d", ret);
	return 0;
}

如果使用递归很容易想到，写出来的代码没有明显的缺陷，那就可以使用递归。但是如果写出来的递归代码，有明显缺陷，例如：效率低下，栈溢出等等。我们可以转化成迭代的方式去解决问题。

总结

思考经典问题

大家可以思考一下，我们将在下次文章中，讲到这两个问题！！！

 ✔✔✔✔✔✔感谢大家的阅读，欢迎指正错误与不足。

代码----------------→【 gitee： https://gitee.com/TSQXG】

联系----------------→【邮箱：2784139418@qq.com】