【C语言刷题】函数递归系列

【C语言刷题】函数递归系列一、编写一个函数实现n的k次方,使用递归实现。(k为整数)二、写一个递归函数DigitSum(n),输入一个非负整数,返回组成它的数字之和三、编写一个函数reverse_string(char*string)(递归实现)

目录

一、编写一个函数实现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,然后取倒数即可,也就是说,他的递推方程应该这样写

【C语言刷题】函数递归系列

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

#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的题目很像,没错,这道题确实思路基本一致。我们来写一下递归函数吧

【C语言刷题】函数递归系列

 那么代码实现如下

#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;
}

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

【C语言刷题】函数递归系列

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

【C语言刷题】函数递归系列

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

#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

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注