5.函数递归练习

目录

TEXT 1 递归方式实现打印一个整数的每一位

TEXT 2 逆序打印整数的每一位

TEXT 3 递归求n（n≥1）的阶乘（不考虑溢出的问题）

TEXT 4 strlen的模拟（递归实现）

TEXT 5 字符串逆序（递归实现）

TEXT 6 计算一个数的每位之和（递归实现）

TEXT 7 递归实现n的k次方

TEXT 8 计算斐波那契数

TEXT 9 走台阶

TEXT 1 递归方式实现打印一个整数的每一位

例如：124，按照顺序打印1 2 4。

思路：

例如：设置一个函数print，打印124的每一位。将124拆分为print（12）和单独打印4；再将12拆分成print（1）和单独打印2；print（1）时，判断1是个位数，停止递归，直接打印1。

#include<stdio.h>

void print(int x)
{
	if (x / 10 != 0)
	{
		print(x / 10);
	}
	printf("%d ", x % 10);
}


int main()
{
    int a = 124;
	print(a);
	return 0;
}

TEXT 2 逆序打印整数的每一位

例如：124，逆序打印4 2 1。

思路：

在递归前实现打印，即可完成逆序打印。

#include<stdio.h>

void print(int a)
{
	if (a / 10 != 0)
	{
		printf("%d ", a % 10);
		print(a / 10);
	}
	else
		printf("%d ", a);

}
int main()
{
	int a = 124;
	print(a);
	return 0;
}

TEXT 3 递归求n（n≥1）的阶乘（不考虑溢出的问题）

思路：

例如：4！拆分为：求3！和*4；3！拆分为：2！和*3；2！拆分为1！和*2；当n=1时，停止递归。

#include<stdio.h>
int fac(unsigned int n)
{
	int sum = 1;
	if (n > 1)
	{
	   sum=fac(n - 1);
	}
	sum *= n;
	return sum ;
}

int main()
{
	unsigned int n = 0;
	scanf("%d", &n);
	printf("%u\n", fac(n));
	return 0;
}

TEXT 4 strlen的模拟（递归实现）

strlen可以求字符串的长度，其结果不包含终止符‘\0’。创建一个函数，模拟strlen的功能。

思路：

我们设置一个函数模拟strlen时，当字符串读取到‘\0’时，迭代结束。

例如：求字符串“abc”的长度，可以拆分为：1+字符串“bc”的长度；求字符串“bc”的长度拆分为：1+求字符串“c”的长度；求字符串“c”的长度拆分为：1+‘\0’；遇到‘\0’停止递归。

#include<stdio.h>

int my_strlen(char* arr)
{
	if (*arr != '\0')
	{
		return 1+my_strlen(arr + 1);
	}
}

int main()
{
	char arr[] = "abcdef";
	printf("%d\n", my_strlen(arr));
	return 0;
}

TEXT 5 字符串逆序（递归实现）

编写一个函数 reverse_string(char * string)（递归实现）//只能传一个参数

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

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

思路：

逆序字符串，可以理解为将第1个字符与最后1个字符交换，第2个与倒数第二个交换......当中间剩余字符为1时，停止迭代。

 交换过程的具体操作：

#include<stdio.h>

   int my_strlen(char* str)
   {
	if (*str != '\0')
	{
		return 1+my_strlen(str + 1);
	}
   }

   void  reverse(char* arr)
   {
	   char temp = 0;//临时变量，存储a的值
	   int left = 0;
	   int right = my_strlen(arr) - 1;
	   temp = *arr;
	   *arr = *(arr + right);//将后面的值赋给前面
	   *(arr + right) = '\0';//将最后一位变成'\0'
	   if (my_strlen(arr + 1) > 1)
	   {
		   reverse(arr + 1);
	   }
	   *(arr + right) = temp;//将临时变量中的值，赋给后面
   }

   int main()
   {
	   char arr[] = "abcdef";
	   reverse(arr);
	   printf("%s\n", arr);
   }

 因为题目要求函数只能传一个参数，所以需要创建很多临时变量。

TEXT 6 计算一个数的每位之和（递归实现）

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

例如，调用DigitSum(153)，则应该返回1 + 5 + 3，它的和是9

输入：153，输出：9

思路：

153可拆分为15和+3；15可拆分为1和+5；1为各位数，停止递归，返回1。

#include<stdio.h>

int DigitSum(n)
{
	int sum = 0;
	if (n / 10 != 0)
	{
		sum =DigitSum(n / 10);
	}
	return sum += n % 10;
}

int main()
{
	unsigned int num = 0;
	scanf("%d", &num);
	printf("%d\n", DigitSum(num));

	return 0;
}

TEXT 7 递归实现n的k次方

利用函数pow（n，k）可以求n的k次方，pow函数的使用需要包含头文件<math.h>。

现在编写一个函数实现n的k次方，使用递归实现。

思路：

需要考虑到k的取值范围

#include<stdio.h>

double my_pow(double n,int k)
{
	if (k > 0)
		return n * my_pow(n, k - 1);
	else if (k == 0)
		return 1;
	else
		return 1.0 / my_pow(n, -k);
}


int main()
{
	double n = 0.0;
	int k = 0;
	scanf("%lf%d", &n, &k);
	printf("%g\n", my_pow(n, k));//%g，打印浮点数时省略无意义的0

	return 0;
}

TEXT 8 计算斐波那契数

斐波那契数：1、1、2、3、5、8、13、21、34、56......从第三项开始，每一项的值等于前两项的和。

思路：

例如当n=5时，第5个斐波那契数=第四个斐波那契数（n-1）+第三个斐波那契数（n-2）

第四个斐波那契数=第三个斐波那契数（n-2）+第二个斐波那契数（n-3）

第三个斐波那契数=第二个斐波那契数1+第一个斐波那契数1。

 

#include<stdio.h>

int fibo(int n)
{
	if (n > 2)
		return fibo(n - 1) + fibo(n - 2);
	else
		return 1;
}


int main()
{
	int n = 0;
	scanf("%d", &n);
	printf("%d\n", fibo(n));
	return 0;
}

TEXT 9 走台阶

n阶台阶，每次可以选择走一阶或者走两阶，那么一共有多少种走法？（1≤n≤30）

思路：

当n=1时，必然只有一种走法；当n=2时，有两种走法；以此类推，当n>2时，便有（n-1）+（n-2）种走法。

#include<stdio.h>

int sum(int n)
{
	if (n > 2)
		return sum(n - 1) + sum(n - 2);
	else if (n == 2)
		return 2;
	else
		return 1;
}

int main()
{
	int n = 0;
	scanf("%d", &n);
	printf("%d\n", sum(n));
	return 0;
}