【C语言】递归问题（爬楼梯）

题目：

楼梯有n阶台阶，一次可以上1阶、2阶或者3阶台阶，使用递归的方法计算出有多少种走完楼梯的方式。

解题思路

图解：

思路：

• 到第一台阶方式：地面到第一台阶的方式，需要 1 步（1） = 1
• 到第二台阶方式：从地面一次走两步（1） +  从台阶 1 走一步（1） = 2
• 到第三台阶方式：从地面一次走三步（1） +  从台阶 2 走一步（1） + 从台阶 1 走两步（2）= 4
• 到第四台阶方式：从台阶 1 一次走三步（1） + 从台阶 2 走两步（2） + 从台阶 3 走一步（4） = 7
• 到第五台阶方式：从台阶 2 一次走三步（2） + 从台阶 3 走两步（6） + 从台阶 4 走一步（7） =  15

可以推导出来：

到台阶 n （n  > 2）的方式：从台阶 （n - 3） 一次走三步 + 从台阶 （n - 2） 走两步， 从台阶 （n - 1） 走一步

-

从第四个开始都是把前面的步骤都加起来，形成一个递归的规则

递归代码：

int steps(int num) {
    if (num < 0)
        return 0;
    if (num == 0 || num == 1)
        return 1;
    if (num == 2)
        return 2;
    return steps(num - 1) + steps(num - 2) + steps(num - 3);
}