[C++知识库]函数递归2

经过了前一章的讲解 ，大家应该对递归有一定的了解了，递归作为非常常用的算法，经常被使用于树这种数据结构。这里需要大量的题目练习，才能熟练的掌握这种方法。

这里就继续练习递归

题目：求一个字符串长度，不允许创建新的变量。

c语言中有一个函数strlen 是存在于string.h这个头文件中的

#define _CRT_SECURE_NO_WARNINGS 1//取消警告
#include<stdio.h>
#include<string.h>
int main() {
	char arr[] = "abc";
	printf("%d", strlen(arr));
	return 0;
}

?如果想自己实现一个strlen这样的一个函数，那么可以来分析一下，这个函数是求得字符串的长度，那么他的返回值应该是要返回字符串长度，也就是一个Int型，一个字符串的结尾为\0，将字符串的首元素地址传入给函数，指针每指向字符串的一个元素，计数器（变量count）就++，指针i向后移动一位，直到指针指向\0则结束

#define _CRT_SECURE_NO_WARNINGS 1//取消警告
#include<stdio.h>
#include<string.h>
int MyStrlen(char* str);
int main() {
	char arr[] = "abc";
	printf("%d\n", strlen(arr));
	printf("%d", MyStrlen(arr));
	return 0;
}
int MyStrlen(char* str) {
	int count = 0;
	while (*str != '\0') {
		count++;
		str++;
	}
	return count;
}

这样的一个MyStrlen就算是简单的实现了strlen这个函数

这是实现strlen最简单的写法，但是这道题当然不会有这么简单，这道题目是不允许创建新的变量的，所以这种方法其实是不可行的。既然这篇文章所讲的是递归，那么这道题目就应该由递归来写。

递归的思想应该是这样MyStrlen(abc)这个函数每一次调用都获得字符串的第一个字符，调用一次就应该是1+MyStrlen(bc)，调用第二次就应该是1+1+MyStrlen(c),再调用最后一次1+1+1+MyStrlen()?这样的函数其实也能求出字符串的长度。函数递归无非是大事化小，小事化了的思想。每次从字符串中取出一个字符

#define _CRT_SECURE_NO_WARNINGS 1//取消警告
#include<stdio.h>
#include<string.h>
int MyStrlen(char* str);
int main() {
	char arr[] = "abc";
	printf("%d\n", strlen(arr));
	printf("%d", MyStrlen(arr));
	return 0;
}
int MyStrlen(char* str) {
	if (*str != '\0') {
		return 1 + MyStrlen(str + 1);
	}
	else {
		return 0;
	}
}

先把代码放上来，当str所指向的不是\0的时候，就再次执行这个函数，如果是\0就递归开始返回，这样的文字描述应该不是非常让人理解，这里大家花时间自己画一个递归的图可能会好很多

?现在再来一道题：求n的阶乘n!（不考虑栈溢出）

n!无非就是1*2*3*………*n,大家应该都会使用循环来解决这个问题，这里我就直接提供代码了

#define _CRT_SECURE_NO_WARNINGS 1//取消警告
#include<stdio.h>
#include<string.h>
int main() {
	int num, ret=1;
	scanf("%d", &num);
	for (int i = num; i > 0; i--) {
		ret *= i;
	}
	printf("%d", ret);
	return 0;
}

当然我们也可以使用递归的的方式

define _CRT_SECURE_NO_WARNINGS 1//取消警告
#include<stdio.h>
#include<string.h>
int fac(int n);
int main() {
	printf("%d", fac(3));
	return 0;
}
int fac(int n) {
	if (n <= 1) {
		return 1;
	}
	else {
		return n * fac(n - 1);
	}
}

?今天又是两道题目，希望大家在看完这两道题目之后对递归有更深的见解。

最近虽然开学了，但是过着还是比较累的，每天早晚自习，高数 线代 大物这三节烧脑的课程总是被放在一起，上完课总是脱层皮，所以写文章的频率也是低了不少，不过每篇文章都是用心之作，希望大家能喜欢且多多点赞