递归问题系列—— C语言

递归训练

递归的问题说难不难，说简单也不简单，关键的点就在找到递归的式子的特性，然后找到递归结束的地方。 递归说白了就是函数通过直接或者间接的方式调用自己 递归用什么语言实现都一样，关键是找到递归的递推公式和递归结束的标志即可

说的再多，还不如直接练呢

一、求和问题

小明准备开始背单词，计划用十天，第一天背一个单词，第二天背第一天多背一个单词，第三天比第二天又多背一个单词，请问，到了第十天的时候，小明总共背了多少单词？

1.1 问题解析

问题可能有点绕口，说白了就是求1到10之间整数之和。用求值公式，循环累加都可以很快实现，然而下面我就用递归给大家介绍一下

1.2 递归讲解

第一天：小明记一个单词，这是已知的量

第二天：小明比第一天多背一个单词，也就是背了1+1个单词

第三天：同理，小明背的单词个数为1+1+1，在第二天的基础上又加了一个

.............

第九天：第八天当天背的单词总数加一

第十天：第九天当天背的单词数再加一

我们已经从头到尾推了一遍，然后再逆推一遍，我们想知道第十天总共背了多少单词，就得实现累加，从第一天到第十天当天背的单词都得知道

逆推过程

欲求第十天当天背得单词数——就得知道第九天当天背得单词数

欲求第九天当天背得单词数——就得知道第八天当天背得单词数

...........

欲求第二天当天背得单词数——我们发现第一天背得单词数告诉我们了

1.3 代码实现

#include
int fac(int n);//声明函数
int main()
{
    int n=10;
    printf("到了第十天总共背了%d个单词",fac(n));
    return 0;
}

int fac(int n)
{
    if(n==1)
        return 1;//递归结束得标志
    else
        return fac(n-1)+ n;
		//函数调用自身，想想欲得到第十天当天背了多少单词 
		//后面得n代表累加得值，代表当天背了多少单词 
}

二、阶乘训练

大多数同学遇到得第一个递归问题基本是阶乘或者汉尼诺问题，阶乘比上面那个问题更简单

2.2 递归讲解

我要求5的阶乘，就得知道5x4! 

欲求4！，得知道4 x 3！

以此类推

欲求 2！，你得求 2 x 1！ ，思路出来了，递归结束得标志是1，求

程序如下：

#include
int main()
{
	int m,n;
	printf("输入你要计算的阶乘的数字：\n");
	scanf("%d",&n);
	m=fac(n);
	printf("%d!=%d\n",n,m);
 } 
 
 int fac(int n){
 	int f;
 	if(n==0||n==1)
 		f=1;//递归结束的标志
 	else
	 	f=n*fac(n-1);//递归的迭代式
 	return f;
 }

三、求年龄

3.1 问题描述

有5个人坐在一起，问第5个人多少岁？他说比第4个人大2岁。问第4个人岁数，他说比第3个人大2岁。问第3个人，又说比第2人大两岁。问第2个人，说比第1个人大两岁。最后 问第1个人，他说是10岁。请问第5个人多大？

 3.2 问题解析

这又是一个递归问题，直接上代码了

#include  

int fac(int n)
{

    if(n==1)
        return 10;
    else
        return fac(n-1)+2;

    
}

int fac(int n);
int main() 
{
	printf("第5个人的年龄是%d岁", fac(5)); 
	return 0;
}