C语言04-函数递归（下）

发表于

「这是我参与11月更文挑战的第11天，活动详情查看：2021最后一次更文挑战」

最近，想复习一下C语言，所以笔者将会在掘金每天更新一篇关于C语言的文章！ 各位初学C语言的大一新生，以及想要复习C语言/C++知识的不要错过哦！ 夯实基础，慢下来就是快！

5.用非递归的方式模拟实现strlen函数

strlen：计算字符串长度的库函数，需要引用string.h头文件。遇到\0停止计数。

strlen和sizeof是一对有点相似的东西，具体的大家可以去看看我之前的文章.关于strlen和sizeof区别的文章链接：
C语言-strlen与sizeof区别

1
2
3
4
5
6
7
8
9
10
11
arduino复制代码//非递归方式
int my_strlen1(char* s)
{
	int count = 0;
	//循环判断 不能用if
	while (*s != '\0')
	{
		s++;
		count++;
	}
	return count;

6.用递归的方式模拟实现strlen函数

图解
image.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
arduino复制代码//递归的方式
int my_strlen2(char* s)
{
	if (*s != '\0')
		return 1 + my_strlen2(s + 1);
	else
		return 0;
}
int main()
{
	char arr[] = "Mango";
	int ret1 = strlen(arr);
	int ret2 = my_strlen1(arr);
	int ret3 = my_strlen2(arr);
	printf("%d %d %d", ret1, ret2, ret3);
	return 0;
}

image.png

7.用非递归实现字符串逆序

方法：使用双指针，一个指向左边，一个指向右边。左指针指向的字符和右指针指向的字符交换。 循环条件为：left < right

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
ini复制代码//非递归方式
void reverse(char* arr)
{
	int len = strlen(arr);	
	//strlen接受的参数是地址，所以写成s  
	//解引用传过去的是char类型的数据，二者不匹配
	char* right = arr + len - 1;
	char* left = arr;  //注意此处不能赋值为0 相当于NULL
	while (left < right)
	{
		char tmp = 0;
		tmp = *left;
		*left = *right;
		*right = tmp;
		left++;
		right--;
	}
}
int main()
{
	char arr[] = "ognam";
	reverse(arr);
	for (int i = 0; i < 5; i++)
	{
		printf("%c", arr[i]);
	}
	return 0;
}

运行结果：

8.用递归实现字符串逆序

图解

image.png

当大家遇到看不懂得递归，也可以像我一样，假设一个例子，然后用展开图来理解一下！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
ini复制代码//递归方式	
void reverse_string(char* arr)
{
	int len = strlen(arr);
	char tmp = *arr;
	*arr = *(arr + len - 1);
 
	*(arr + len - 1) = '\0';
	if (strlen(arr + 1) >= 2)
		reverse_string(arr + 1);
 
	*(arr + len - 1) = tmp;
}
int main()
{
	char arr[] = "ognam";
	reverse_string(arr);
	for (int i = 0; i < 5; i++)
	{
		printf("%c", arr[i]);
	}
	return 0;
}

image.png

9.用递归计算一个数拆分成每一位之后的每位之和

图解

image.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
arduino复制代码int DigitSum(int n)
{
	if (n)
		return n % 10 + DigitSum(n / 10);
	else
		return 0;
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	int sum = DigitSum(n);
	printf("%d", sum);
	return 0;
}

运行结果：

10.用递归实现计算n的k次方

图解

image.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
arduino复制代码int my_pow(int n, int k)
{
	//一个数的0次方=1
	if (k == 0)
	{
		return 1;
	}
	else if (k >= 1)
		return my_pow(n, k - 1)*n;
}
int main()
{
	int n = 0;
	int k = 0;
	scanf("%d %d", &n, &k);
	int ret1 = pow(n, k);
 
	int ret2 = my_pow(n, k);
	printf("%d  %d", ret1, ret2);
}

运行结果：

11.用非递归求第n个斐波那契数

图解

image.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
arduino复制代码//8.求第n个斐波那契数
//递归方式
//方式1：
int Fic(int n)
{
	return n <= 2 ? 1 : Fic(n - 1) + Fic(n - 2);
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	int ret = Fic(n);
	printf("%d", ret);
	return 0;
}

此种写法需要计算很多重复的数，效率低！

方法2：迭代计算

image.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
ini复制代码//方式2
int Fic(int n)
{
	//思路：a, b, c  算出a + b的值放到c，   下一次：将b的值给a，将c的值给b  循环计算
	//从第3个斐波那契数开始算，计算1次，计算第4个斐波那契数要计算2次
	//- - 》》所以计算第n个要计算n - 2次
	int a = 1;//第1个斐波那契数
	int b = 1;//第2个斐波那契数
	int c = 0;
	while (n > 2)
	{
		c = a + b;
		a = b;
		b = c;
		n--;
	}
	return c;
	//当n是1或2时  不进入循环 返回c = 0  err
	//所以c初始化为1
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	int ret = Fic(n);
	printf("%d", ret);
	return 0;
}

运行结果：

递归习题练习到这里就差不多结束了，明天，我会给大家带来两个经典的递归问题：青蛙跳台阶和汉诺塔问题！欢迎大家持续关注！

今天就先到这吧~感谢你能看到这里！希望对你有所帮助！欢迎老铁们点个关注订阅这个专题！ 同时欢迎大佬们批评指正！

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%