一.递归练习题

1.使用递归的方式，输出n的阶乘（不考虑溢出问题）

参考信息：

假若函数名为Fac()，下列为阶乘的计算公式：

当n的值小于等于1的时候阶乘的结果就为1，当n的值大于1的时候阶乘的结果为n*Fac(n-1)，我们可以发现当n<=1的时候可以直接使用代码：

return 1;

来返回结果，但是当n的值大于1的时候则需要将n的值乘以Fac(n-1)，这就使用到了简单递归，如以下代码：

return n*Fac(n - 1);

所以我们可以将代码写成如下形式：

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
int Fac(int n){
	if (n <= 1){
		return 1;
	}
	else{
		return n*Fac(n - 1);
	}
}
int main(void){
	int n = 0;
	scanf("%d",&n);
	int ret = Fac(n);
	printf("%d\n",ret);
	return 0;
}

在main()函数中我们创建了两个变量n与ret，其中n来接收用户输入的值，ret来接收函数Fac()的返回值，最后进行输出，Fac()函数中首先使用if语句来判断n的值，若n<=1则直接返回1，其他情况（n>1）则返回 n*Fac(n-1) 的值，这样子我们就实现了阶乘，如图所示：

2.利用函数的递归，求第n个斐波那契数列

斐波那契数列就是前两个数字之和等于第三项的值，如 1 1 2 3 5 8 13 21 34····

数学上也有专门的公式来计算斐波那契数列，如图所示（假设计算斐波那契数列的函数名为Fib()）：

当n的值小于等于2的时候则输出1，若n的值大于2的时候则输出 Fib(n-1)+Fib(n-2) 的值，与上面相似，当n的值小于等于2的时候我们可以写：

return 1;

若n的值大于2我们则可以写：

return Fib(n-1)+Fib(n-2);

所以我们代码可以写成如下形式：

#include<stdio.h>
#include<windows.h>
int Fib(int n){
	if (n <= 2){
		return 1;
	}
	else{
		return Fib(n - 1) + Fib(n - 2);
	}
}
int main(void){
	int n = 0;
	scanf("%d",&n);
	int ret = Fib(n);
	printf("%d\n",ret);
	return 0;
}

当我们输入10的时候则程序会输出55，我们进行计算后发现21+34的值正好等于55，程序满足了我们的要求，如图所示：

但是这段代码也有一些问题，比如说当我们输入60的时候程序就会不显示任何东西，证明代码需要进行调整，我们下一章节再详谈   

                                                                                                                2023/8/18

                                                                                                                   王起舟