C语言递归解决年龄问题

问题描述

有5个人坐在一起，问第5个人多少岁，他说比第4个人大2岁。问第4个人多少岁，他说比第3个人大2岁。问第3人多少岁，他说比第2个人大2岁。问第2个人多少岁，他说比第1个人大2岁。最后问第1个人，他说他是10岁。编写程序，当输入第几个人时求出其对应的年龄。

问题分析

该问题是一个递归问题。要求第5个人的年龄，必须先知道第4个人的年龄，显然第4个人的年龄也是未知的，但可以由第3个人的年龄推算出来。而想知道第3个人的年龄又必须先知道第2个人的年龄，第2个人的年龄则取决于第1个人的年龄。

又已知每个人的年龄都比其前一个人的年龄大2，因此根据题意，可得到如下几个表达式：
age(5)=age(4)+2
age(4)=age(3)+2
age(3)=age(2)+2
age(2)=age(1)+2
age(1)=10

归纳上面5个表达式，用数学公式表达出来为：


求解第n个人的年龄分成两个阶段。第一个阶段是“回推”过程，第二个阶段是“递推”过程。

在“回推”过程中，利用的是n>1时的公式age(n-l)+2。要求的是第n个人的年龄，因此首先将第n个人的年龄回推到第n-1个人的年龄，但第n-1个人的年龄仍然未知，因此需要继续回推到第n-2个人的年龄，第n-2个人的年龄仍然未知，需要继续向前回推，如此下去，一直回推到第1个人的年龄。而第1个人的年龄是已知的，因此，第一阶段的 “回推”结束。

在“递推”过程中，从第1个人的年龄可以推出第2个人的年龄，从第2个人的年龄可以推出第3个人的年龄，如此下去一直递推到第5个人的年龄。

算法设计

理解了问题分析中的递归处理过程后，算法设计就非常简单了。只需要将公式转换成一个函数，然后用main()函数调用它就可以了。

下面是完整的代码：

#include<stdio.h>
int age(int n)
{
    int x;
    if(n == 1)
        x=10;
    else
        x=age(n-1)+2;
    return x;
}
int main()
{
    int n;
    printf("请输入n值：");
    scanf("%d", &n);
    printf("第%d个人的年龄为%d\n", n, age(n));
    return 0;
}

运行结果：
请输入n值：5
第5个人的年龄为18

知识点补充

由该题的分析过程可知，递归的问题都可以分为“回推”和“递推”两个阶段。而且必须存在一个能够结束递归过程的条件，如本题中的age(l)=10,否则递归过程会无限制地进行下去而无法结束。

下面对递归法做下总结。

递归是设计和描述算法的一种强有力的工具。能够釆用递归来描述的算法通常具有如下的特征：为求解规模为n的问题，首先要将它分解成规模较小的问题，然后通过这些小问题的解，能够方便地构造出大问题的解。

同时，这些规模较小的问题也能够采取同样的分解方法分解成规模更小的问题，并能够通过这些更小的问题的解构造出规模较大的问题的解。特别地，当问题规模n=0或n=1时，能直接获得问题的解。

递归算法的执行过程分为“回推”和“递推”两个阶段：

1. 在回推阶段，是把较复杂的问题（规模为n）的求解递推到比原问题简单一些的问题（规模小于n）的求解。例如本例中，要求解age(n)，先把它递推到求解age(n-l)，而要计算age(n-1)，又必须先计算age(n-2)，依次类推，直到计算age(1)为止。需要注意的是，在递推阶段，必须要有能够终止递归的条件。如本例中n为1时，递推可终止。
2. 在递推阶段，当获得最简单情况的解时，如本题中得到age(1)的值，逐级返回，依次得到较复杂问题的解，最终获得所求问题的解。

在编写递归函数时需要注意，函数中定义的局部变量和形式参数只在当前的调用层有效，当回推到简单问题时，原来调用层中的局部变量和参数都被隐藏起来。每一个简单问题层中都有自己的局部变量和参数。