递归之研究

#include<stdio.h>
#include<stdlib.h>
int count(int n);
/*count how many ways to climb up N steps stairs.*/
int main (int argc, char *argv[])
{
    int n,ct;
    printf("please input n:\n");
    scanf("%d",&n);
    ct=count(n);
    printf("there are %d ways to climb up N steps stairs!\n",ct);
    system("PAUSE");
    return 0;
}
int count(int n)
{
    if(1==n)
        return 1;
    else if(2==n)
        return 2;
    else return count(n-1)+count(n-2);
}

我觉得学习最后先从看程序开始然后在去找相关知识点系统学习，这样会理解的比较深刻！

以上代码解决了一个实际问题：

【问题描述】梯有N阶，上楼可以一步上一阶，也可以一步上二阶。编写一个程序，计算共有多少中不同的走法。

【思路】看到此题目容易想到用递归的方法来做，因为递归是一种描述和解决结构自相似问题的基本算法，而N阶楼梯问题和N-1阶、N-2阶的结构完全相同。
     解决递归问题可以分为两个部分，第一部分是一些特殊（基础）情况，用直接法解，即始基；第二部分与原问题相似，可用类似的方法解决（即递归），但比原问题的规模要小。
     定义int count(int n)函数求解N阶楼梯的走法，基于上述思想，可知：

• N阶楼梯问题的始基是N==1、N==2两种情况；
• 上楼可以一步上一阶，也可以一步上二阶，当上一阶时问题规模变为N-1，当上二阶时问题规模变为N-2，所以总的情况为count(n-1)+count(n-2)

实际解题思路是比较重要的我们如何再能把实际问题转换为递归求解这个是需要深入理解的！

第一步我们先来理解这个程序如何运行。

当我们看到程序提示输入，我们现在输入5.

这个时候程序应该执行到count（5）这个位置，我们来详细查看一下这里的执行过程

n = 5; return count(5-1)+count(5-2); 程序继续执行调用到

n = 4; return count(4-1)+count(4-2);

n = 3; return count(3-1)+count(3-2);

n = 2; return 2;

n = 1; return 1;

通过这个推理我们就可以知道count（2）= 2； count（1）= 1；count（3）= count（1）+count（2）= 1+2；count（4）= 3+2；count（5）= 5+3  的值，正向推理以后我们再反向找回去就能得到count(5)的结果了！ 8.