一、编写一个函数实现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<stdio.h> 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，方便递归调用这个新字符串，等这个递归结束后，再把我们延迟交换的这个字符给补上即可
总结
本节课主要讲解了三道经典的例题，其中第三题需要仔细理解一下。
