函数--递归调用

1.怎么写出一个递归函数

step1，写好公式

公式是怎么得出的？一般来说通过数学上的归纳演绎、总结得出，具体看下面的例子。

step2，一定要写结束条件

这一步比较简单，还是得到公式比较关键。

2.走楼梯

Description

假如有n个台阶，一次只能上1个台阶或2个台阶，请问走到第n个台阶有几种走法？为便于读者理解题意，这里举例说明如下：假如有3个台阶，那么总计就有3种走法：第一种为每次上1个台阶，上3次；第二种为先上2个台阶，再上1个台阶；第三种为先上1个台阶，再上2个台阶。输入为n，输出为走到第n个台阶有几种走法
Input
比如输入是3

Output
如果输入是3，走到第3个台阶的走法总计有3种，1,1,1 和 1,2 和2,1，输出为3

2.1 找公式

• 归纳，设台阶共n级，
• 若n=1，则共1种；
• 若n=2，则有2种；
• 若n=3，则有3种；
• 若n=4，则有？

n = 4
1 1 1 1
1 1 2
1 2 1
2 1 1
2 2

n=5
1 1 1 1 1
1 1 1 2
1 1 2 1
1 2 1 1
2 1 1 1
1 2 2
2 2 1
2 1 2

• 若n=4，共有5种；
• 若n=5，共有8种。
  故由归纳演绎可知，step(n)= step(n-1)+step(n-2)，公式找到。

2.2 确定结束条件

首先，我们要知道调用函数f(n)，这个f(n)实际上代表了函数的返回值。在走楼梯问题中，当n=3时，return step(1)+step(2) ，而再往下台阶不可能等于0或小于0，所以找到了结束条件。

2.3 函数实现

#include <stdio.h>

//递归调用
int step(int n)
{
    if(1 == n || 2 == n) //第二步，确定结束条件
    {
        return n;
    }
    return step(n-1) + step(n-2); //第一步，写好公式
}

int main()
{
    int n; //几级台阶
    int num = 0; //共几种走法
    scanf("%d", &n);
    num = step(n);
    printf("%d\n", num);
    return 0 ;
}