[c语言日寄]递归进阶：深度

siy2333

发布于 2025-02-05 12:47:29

4300

代码可运行

文章被收录于专栏：来自csdn的博客来自csdn的博客

运行总次数：0

代码可运行

哈喽大家好啊，经历了残忍的期末周之后，鼠鼠我啊~ 又复活了呢~ 在阔别许久之后的第一次快乐刷题中，我遇到了这样的一道题：

题目

题目初探

如题，这个其实一个简单的for循环就能搞定的题目，结果要求用递归，一下子就变难了好多。

思路分析

储存字符串

为了方便操作，我们可以使用数组储存字符！

char arr[] = "abcdefg";

计算字符串长度

由于不能使用strlen()等函数，需要我们手动计算字符串长度。我们从字符串的第一个字符开始逐字遍历，直到遇到空字符’\0’为止，统计遍历的字符个数即为字符串长度。

int	suo = 0;
while (arr1[suo] != '\0')suo++;
suo = suo-1;//字符串长度减一，以对应最后一个有效字符

递归函数设计

如何反转一个字符串呢？左边第一个和右边第一个交换，左边第二个和右边第二个交换……没错！我们需要两个对象！左边一个，右边一个。交换很容易实现，但是怎么样定位左边和右边的呢？

双指针！

如果我定义一个指针，指向左边第一个，每执行一次就往后推移一下；再定义另一个指针，指向右边第一个，每执行一次就往前推进一下……

那不就解决定位的问题了吗！

char* double_point(char* arr1, char* arr2);

终止条件

众所周知~递归函数需要有明确的终止条件，否则会导致无限递归，导致内存砰的一下满了。为了避免这种惨状发生，我们需要一个结束递归的条件，也就是终止交换操作的条件：

当起始位置指针大于或等于结束位置指针时，说明已经完成了整个字符串的反转，递归终止。

字符串打印函数

利用指针遍历字符串打印，方便检验是否反转成功~

void print_arr(char* arr) {
    int i = 0;
    while (arr[i] != '\0') {
        printf("%c\t", arr[i]);
        i++;
    }
}

完整代码

//双指针实现
#include<stdio.h>

char* double_point(char* arr1, char* arr2);
void print_arr(char* arr);


int main() {

	char arr[] = "abcdefg";

	print_arr(arr);
	printf("\n");

	double_point(arr, NULL);

	print_arr(arr);

	return 0;
}


char* double_point(char* arr1,char* arr2) {

	if (arr2 == NULL) {
		//查找对应索引
		int	suo = 0;
		while (arr1[suo] != '\0')suo++;

		suo = suo-1;

		arr2 = arr1 + suo;
	}

	//递归退出
	if (arr1 >= arr2)return NULL;

	//元素交换
	char a = 0;

	a = *arr1;
	*arr1 = *arr2;
	*arr2 = a;

	//递归
	double_point(++arr1, --arr2);

}

void print_arr(char* arr) {

	int a = 0;
	while (arr[a] != '\0') {
		printf("%c\t", arr[a]);
		a++;
	}

	return;
}

进阶解法

我们已经顺利解决了问题！但~ 是~ 聪明的小朋友这时候就要问了 ~ 啊不对啊，明明题目中给出的函数只有一个形参，你怎么能擅自加到两个指针呢？这不是不符合题意吗！欸，莫急，我还有只需要一个指针的解法！

思路分析

既然只能有一个参数传入，那么就函数应该长这样：

char* single(char*arr)；

可是，我们只能用一个指针来进行交换量的选定，这说明另一个交换量需要我们用其他方式来实现锚定。仔细回想，什么东西可以传递到函数里面？参数、全局变量……还有静态变量！静态变量是在程序的整个运行期间都存在且只初始化一次的变量，它不会由于函数的递归调用而被反复初始化。因此，我们可以设立一个标记递归深度的静态变量：

static int depth = 0;

只要配合depth++，我们就能实现传递递归层数；第一次递归，目标量1是arr[0],目标量2是arr[suo]，(suo 是最后一个有效字符的索引) 第二次递归，目标量1是arr[1],目标量2是arr[suo - 1]……

使用single（arr+1）可以实现目标量1的推移，使用arr[suo - depth]可以实现目标量2的推移。

那么，还有最后一个问题，既然静态变量无法每次调用都初始化，那要怎么实现成功转换一个字符串结束后，初始化递归深度呢？

很简单，只要在递归模块后添加一个depth–就可以了。具体不太好描述，大家可以结合完整代码体会体会awa。

完整代码

#include<stdio.h>

char* single(char* arr);
void print_arr(char* arr);


int main() {

	char arr[] = "abcdefgh";

	print_arr(arr);
	printf("\n");

	single(arr);

	print_arr(arr);

	return 0;
}

char* single(char*arr) {
	static int depth = 0;
	static int mid = 0;

	//字符串长度
	int suo = 0;
	while (arr[suo] != '\0')suo++;
	suo--;

	//记录中值
	if (depth == 0) {
		mid = suo / 2;
	}

	
	if (suo > mid) {
		//交换
		char a = arr[0];
		arr[0] = arr[suo - depth];
		arr[suo - depth] = a;
		depth++;
		single(arr+1);
	}
	else{
		return NULL;
	}
	//深度回调
	depth--;
}

void print_arr(char* arr) {

	int a = 0;
	while (arr[a] != '\0') {
		printf("%c\t", arr[a]);
		a++;
	}

	return;
}