目录
二、写一个递归函数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<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,方便递归调用这个新字符串,等这个递归结束后,再把我们延迟交换的这个字符给补上即可
总结
本节课主要讲解了三道经典的例题,其中第三题需要仔细理解一下。
今天的文章【C语言刷题】函数递归系列分享到此就结束了,感谢您的阅读,如果确实帮到您,您可以动动手指转发给其他人。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/30331.html