上楼梯题解

上楼梯问题是一个经典的递归问题。问题描述如下：一个人要上 n 级台阶，每次只能上 1 级或 2 级，问有多少种不同的方法可以走完这 n 级台阶。

使用递归算法来解决上楼梯问题，可以写出如下的递归函数：

int climbStairs(int n) {
    if (n == 1) {
        return 1;
    } else if (n == 2) {
        return 2;
    } else {
        return climbStairs(n-1) + climbStairs(n-2);
    }
}

在这个递归函数中，当 n 等于 1 时，返回 1；当 n 等于 2 时，返回 2；否则，返回上一级和上两级的方法之和。这个递归函数可以计算任意一个台阶数的不同上楼梯方法数。

例如，当 n 等于 4 时，这个递归函数的调用过程如下：

climbStairs(4)
= climbStairs(3) + climbStairs(2)
= (climbStairs(2) + climbStairs(1)) + 2
= 2 + 1 + 2
= 5

因此，当 n 等于 4 时，有 5 种不同的上楼梯方法。

需要注意的是，递归算法的时间复杂度可能会很高，因为有很多重复计算。例如，当 n 等于 5 时，climbStairs(3) 会被计算两次。因此，为了避免重复计算，可以使用动态规划等方法来优化递归算法。