一、什么是递归

简单地说，就是如果在函数中存在着调用函数本身的情况，这种现象就叫递归。

1、一个问题的解可以分解为几个子问题的解
2、这个问题与分解之后的子问题，除了数据规模不同，求解的思路完全相同
3、存在终止条件

以阶层函数为例,如下, 在 factorial 函数中存在着 factorial(n - 1) 的调用，所以此函数是递归函数：

public int factorial(int n) {
    if (n < =1) {
        return 1;
    }
    return n * factorial(n - 1)
}

二、实战演练

2.1、爬楼梯问题

解法一：递归思路


弊端：存在重复计算，时间复杂度高

优化以后：用hashMap来保存n个楼梯，对应的解法数m，先去hashMap取。取不到，再去计算！