第三站：函数（第三幕）递归训练

目录

一、编写一个函数实现n的k次方，使用递归实现。（k为整数）

二、写一个递归函数DigitSum(n)，输入一个非负整数，返回组成它的数字之和

三、编写一个函数 reverse_string(char * string)（递归实现）

总结

---

一、编写一个函数实现n的k次方，使用递归实现。（k为整数）

 这道题我们其实就很容易联想到库函数中就有一个pow函数，这道题的本质就是想让我们模拟这个pow函数。

那么该如何模拟呢？我们的次方无非就是0，大于0，小于三种情况，等于0最简单，因为任何数的0次方都等于1，大于0呢？那就相当于n*n的k-1次方。小于零的话，那不就是大于0的倒数吗，我们将k改为-k，然后取倒数即可，也就是说，他的递推方程应该这样写

 那有了递推函数，写出答案就轻而易举，代码如下

#include<stdio.h>
double Pow(int n, int k)
{
	if (k == 0)
	{
		return 1;
	}
	else if (k > 0)
	{
		return  n * Pow(n, k - 1);
	}
	else
	{
		return 1.0 / Pow(n, -k);
	}
}
int main()
{
	int n;
	int k;
	scanf("%d %d", &n, &k);
	double ret = Pow(n, k);
	printf("%lf", ret);
	return 0;
}

二、写一个递归函数DigitSum(n)，输入一个非负整数，返回组成它的数字之和

例如，调用DigitSum(1729)，则应该返回1+7+2+9，它的和是19

输入：1729，输出：19

这道题，不知道大家有没有感觉和上一篇文章种分解1234的题目很像，没错，这道题确实思路基本一致。我们来写一下递归函数吧

 那么代码实现如下

#include
int DigitSum(int n)
{
	if (n > 9)
	{
		return DigitSum(n / 10) + n % 10;
	}
	else
	{
		return n;
	}
}
int main()
{
	int n;
	scanf("%d", &n);
	int ret = DigitSum(n);
	printf("%d", ret);
	return 0;
}

三、编写一个函数 reverse_string(char * string)（递归实现）

实现：将参数字符串中的字符反向排列，不是逆序打印。

要求：不能使用C函数库中的字符串操作函数。

比如:char arr[] = "abcdef"   逆序之后数组的内容变成：fedcba

这道题很多人看到后肯定是一脸懵了。没有什么思路，但是不要怕。我们先一步一步看。递归我们可能一开始想不到，但是循环的方式我们应该还是可以想到的。首先看下图，这是我们的字符串

 我们想要进行逆序，那我们可不可以，利用一下之前二分查找时候，我们使用了左下标和右下标的方法，我们将第一个和最后一共进行交换，然后第二个和倒数第二个进行交换，这样一直交换下去，就可以解决了，而循环结束的条件也和二分查找那个一致，左下标小于等于右下标即可。那我们简单的实现一下吧。

#include<stdio.h>
int my_strlen(char* str)
{
	int count = 0;
	while (*str != '\0')
	{
		str++;
		count++;
	}
	return count;
}
void reverse_string(char arr[])
{
	int left = 0;
	int right = my_strlen(arr) - 1;
	while (left <= right)
	{
		int tmp = 0;
		tmp = arr[left];
		arr[left] = arr[right];
		arr[right] = tmp;
		left++;
		right--;
	}
}
int main()
{
	char arr[] = "abcdef";
	reverse_string(arr);
	printf("%s", arr);
	return 0;
}

上面这段代码中，我们的参数是用一个数组，可是题目要求的是指针，那该如何解决呢，其实数组传参传的就是首元素地址，改成指针当然没问题，但是下面的使用数组的方式进行交换有人就感觉很乱了， 其实这里采用数组的方式也是可以的，我们后期会着重讲解，这里我们可以把他改写成指针的方法。代码如下所示

#include<stdio.h>
int my_strlen(char* str)
{
	int count = 0;
	while (*str != '\0')
	{
		str++;
		count++;
	}
	return count;
}
void reverse_string(char* arr)
{
	int left = 0;
	int right = my_strlen(arr) - 1;
	while (left <= right)
	{
		int tmp = 0;
		tmp = *(arr+left);
		*(arr+left) = *(arr+right);
		*(arr+right) = tmp;
		left++;
		right--;
	}
}
int main()
{
	char arr[] = "abcdef";
	reverse_string(arr);
	printf("%s", arr);
	return 0;
}

这样确实可以使用使用循环的方式解决了问题，可是这还不够，因为我们的需求是采用递归。递归该如何想呢？

 上图是我们需要交换的字符串，我们可以这样想，我们先交换a和f，然后递推调用交换bcde这个段字符串，然后继续交换b和e，然后递推调用交换cd，然后交换c和d，递推调用空字符串，遇到空字符串，就返回。这样想的话，似乎思路已经出来了。我们画一下函数公式吧。

 注意这里的只是为了方便理解所写出的一个公式，可能并不是很严谨，这是一个伪代码。但是根据这个我们已经可以写出我们的代码了，代码实现如下

#include<stdio.h>
int my_strlen(char* str)
{
	int count = 0;
	while (*str != '\0')
	{
		str++;
		count++;
	}
	return count;
}
void reverse_string(char* arr)
{
	int right= my_strlen(arr) - 1;
	if (*arr != '\0')
	{
		char tmp;
		tmp = *arr;
		*arr = *(arr + right);
		*(arr+right) = '\0';
		reverse_string(arr + 1);
		*(arr + right) = tmp;
	}
}
int main()
{
	char arr[] = "abcdef";
	reverse_string(arr);
	printf("%s", arr);
	return 0;
}

这就是我们的代码，唯一需要注意的一个坑就是，交换后，右边的得先变为\0，方便递归调用这个新字符串，等这个递归结束后，再把我们延迟交换的这个字符给补上即可

---

总结

本节课主要讲解了三道经典的例题，其中第三题需要仔细理解一下。