什么是递归呢？
一个大的问题f(n)可以被拆解为小一点的问题f(n-1)和f(n-2)，……直到然后拆到最小的问题f(1)和f(2)。很多人把从大往小算的形式称作递归
我们用一个题目引入：
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
我们用 f(x) 表示爬到第 x 级台阶的方案数，考虑最后一步可能跨了一级台阶，也可能跨了两级台阶，所以我们可以列出如下式子：
f(x)=f(x−1)+f(x−2)
它意味着爬到第 x级台阶的方案数是爬到第x−1级台阶的方案数和爬到第x−2级台阶的方案数的和。
以上递推性质为斐波那契数列。因此，本题可转化为 求斐波那契数列的第x项，区别仅在于初始值不同。
爬楼梯问题： f(0)=1 , f(1)=1 , f(2)=2 。
斐波那契数列问题： f(0)=0 , f(1)=1 , f(2)=1 。
因此本题 f(0)=1，f(1)=1，f(2)=1，可由此编写递归函数。
public static int climbStairs(int n) {
if(n==1) {
return 1;
}
if(n==2) {
return 2;
}
return climbStairs(n-1)+climbStairs(n-2);
}
这样我们可以得出本题的解，但是此方法并不是最优，通过递归很容易发生的问题就是重复计算，这里只是以题目引出递归的方法。
力扣官方题解链接：https://leetcode.cn/problems/climbing-stairs/