【C语言】函数递归编程题

题目一：

题目二：

题目三：

题目四：

总结

题目一：

题目：接受一个整型值（无符号），按照顺序打印它的每一位。（递归完成）

列如：

输入：1234，输出1 2 3 4

题目解析：

接受一个整型值（无符号），那就是输入的数不能为负数
持续获得整数的个位值，方法为：n % 10得到个位，n / 10 得到除了个位以外的数
重复n%10，n/10，n%10.....直到n%10 = n，就把一个整数拆分了
需要按照顺序打印，这里使用递归是比较合适的
我们使用大事化小的方式思考，当n<=9的时候，表示这个整数只剩下/只有个位，那就说明该整数为n本身
当n>9的时候，可以将整数1234拆分为，123和4，因为4是很容易得到的，对1234%10=4，那我们让123先打印在屏幕上，然后再打印4
以此类推，123拆分为12和3，12拆分为1和2，当想再拆分1时，发现1<=9，则只剩个位，然后将1本身进行打印，再往前进行打印
下面是图解：

代码实现：

//接受一个整型值（无符号），按照顺序打印它的每一位。
//例如：输入：1234，输出 1 2 3 4.
void Print(unsigned int n)
{
	//n>9表示n不止1位数
	if (n > 9)
		// n/10 --> 得到除个位的其它数
		Print(n / 10);
	//当n<=9时，说明此时n只有一位数，进行n%10=n
	printf("%d ", n % 10);
}
int main()
{
	//unsigned int 表示无符号整型
	unsigned int num = 0;
	scanf("%u", &num); //%u为无符号整形的格式化字符
	Print(num); //用于按照顺序打印每一位数
	return 0;
}

对代码进行图解：

题目二：

题目：编写函数不允许创建临时变量，求字符串的长度。（递归/迭代）

题解：

求字符串的长度，在C语言中有一个库函数strlen，题目要求编写函数，那就是说让我们模拟实现strlen库函数了，我们先从简单方式开始，用迭代的方式模拟实现strlen，并且允许创建临时变量：

//使用临时变量，迭代方式模拟实现strlen
#include <string.h>
int Strlen(char* parr)
{
	int count = 0;
	while (*parr != '\0')
	{
		count++;
		parr++;
	}
	return count;
}
int main()
{
	char arr[10] = "abcdef";
	int n = Strlen(arr);
	printf("%d\n", n);
	return 0;
}

按照这个思路，我们想想如何不使用临时变量，迭代方式模拟实现strlen呢？其实可以利用指针的计算特性，创建一个指向parr的指针，该指针不算临时变量，然后让该指针进行遍历，直到指向'\0'，然后利用指针计算特性：尾地址 - 首地址 = 元素个数。（因为地字符串地址中的每个字符地址是连续的）

//不使用临时变量，迭代方式模拟实现strlen
#include <string.h>
int Strlen(char* parr)
{
	char* tmp = parr;
	while (*tmp != '\0')
	{
		tmp++;
	}
	return tmp - parr;
}
int main()
{
	char arr[10] = "abcdef";
	int n = Strlen(arr);
	printf("%d\n", n);
	return 0;
}

利用递归模拟实现strlen就得转变一下思路了，使用大事化小思想，当是空字符时，字符个数为0，当*parr!='\0'则最少有一个字符时，字符个数为1，那我们可以把字符串看出一个整体，进行拆分，一个字符+ (n-1)个字符，一直拆，一个字符 + (n-2)个字符.....，直到变为空字符，再从0开始往回相加，具体看代码：

//不使用临时变量，递归方式模拟实现strlen
#include <string.h>
int Strlen(char* parr)
{
	while (*parr != '\0')
	{
		//!='\0'时最少1个字符
		return 1 + Strlen(parr + 1); //parr+1 表示拿到下一个字符的地址
	}
	return 0; //当为空字符时
}
int main()
{
	char arr[10] = "abcdef";
	int n = Strlen(arr);
	printf("%d\n", n);
	return 0;
}

注意：

不要写出parr++，因为这是后置++，是先将地址传过去了，才进行+1操作，这就不符合存在限制条件，当满足这个限制条件的时候，递归便不再继续这个条件了。
每递归一次，都会创建一个临时指针变量str，因此parr++操作，先把原本的地址传递过去了，然后自己在+1，指向下一个字符，但并没有影响到其它的parr，parr+1也只存在于调用前那块parr空间，因此程序陷入死循环，直到栈溢出。
因此，在递归时，尽量不要写前置++与后置++，因为会把parr指针的指向改变。修改本身，建议parr+ 1，这种不会修改本身，只是得到当前指向的下一个地址。

代码图解：

题目三：

题目：求n的阶乘。（不考虑溢出）

题解：

用递归求n的阶乘，当n为<2时，阶乘为1，当n>=2时，可以看出n * (n-1)个阶乘，因为一个阶乘往往是从1乘到n，因此可以进行拆分，直到n<2，拆分不了了，开始返回相乘。（从后往前乘）
因此得出公式：

代码如下：

//递归求n的阶乘
int factorial(int n)
{
	if (n>=2)
	{
		return n * factorial(n-1);
	}
	return 1;
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	int sum = factorial(n);
	printf("%d\n", sum);
	return 0;
}

当然，使用 factorial 函数求10000的阶乘（不考虑结果的正确性），程序会崩溃。因为栈区的空间是有上限的，超过了就会导致栈溢出。对于这种情况，最好的解决办法就是将递归改写成非递归：

//迭代求n的阶乘
int factorial(int n)
{
	int res = 1;
	for (int i = 1; i <= n; i++)
	{
		res *= i;
	}
	return res;
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	int sum = factorial(n);
	printf("%d\n", sum);
	return 0;
}

当然了，结果肯定是不对的，这里解决的只是防止栈溢出的情况，要想结果正确，需要分配内存更大的类型，因为res 为整型，当数值太大，整型存储不下，就会溢出。

题目四：

题目：求第n个斐波那契数。（不考虑溢出）

题解：

斐波那契数为：前两个数相加 = 当前数
要使用递归进行求解，那么需要考虑限定条件，当求n<3时，斐波那契数均为1，因为想形成斐波那契数，最少需要3个数。
然后我们思考n>2的情况，（第n-1个斐波那契数）+（第n-2个斐波那契数），递归，直到n<3，返回1
代码如下：

//求第n个斐波那契数(递归实现)
int fibonacci(int n)
{
	if (n>2)
	{
		return fibonacci(n - 1) + fibonacci(n - 2);
	}
	return 1;
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	int fibonacci_number = fibonacci(n);
	printf("%d\n", fibonacci_number);
	return 0;
}

代码图解：

但是我们发现有问题：在使用这个函数的时候如果我们要计算第50个斐波那契数字的时候特别耗费时间。为什么呢？我们可以记一下数：

int count = 0;//全局变量
int fibonacci(int n)
{
	//统计整个递归下来，求第3个斐波那契数会执行多少次
	if (n == 3)
	{
		count++;
	}
	if (n>2)
		return fibonacci(n - 1) + fibonacci(n - 2);
	return 1;
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	int fibonacci_number = fibonacci(n);
	printf("%d\n", fibonacci_number);
	return 0;
}

当计算第40个斐波那契数时，n == 3的执行次数已经很大了，我们看看下面这张图：

我们发现会有很多重复的次数被重复计算，因为我们是从后往前计算的，看公式：Fb(n-1) + Fb(n-2) 这种计算方式会有很多重复的计算，比如算第10个斐波那契数：

有很多重复的计算。那如何解决呢？其实我们可以使用迭代的方式进行计算：（从前往后算），还是求第10个斐波那契数：

代码如下：

//迭代求第n个斐波那契数
int fibonacci(int n)
{
	int a = 1;
	int b = 1;
	int c = 1;
	while (n>2)
	{
		c = a + b;
		a = b;
		b = c;
		n--;
	}
	return c;
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	int fibonacci_number = fibonacci(n);
	printf("%d\n", fibonacci_number);
	return 0;
}