递归介绍

使用递归时需要满足的条件

1 解决该问题需要分解成几个子问题
2 分解后的子问题的解决思路除了数据规模不同，求解思路完全一样。
3 将问题分解成子问题，子问题又可以分解成子子问题并且要存在终止条件。

举例：

1 去电影院看电影，如果你不知道自己目前所处第几排，你可以询问前面一排是第几排，前面一个还不知道自己是第几排，可以继续往前问，一直问道第一排。让后第一排的人告诉问他的人，最终知道你所处的第几排。公式为 f(n) = f(n-1)+1,f(n) 表示最终结果，f(n-1)前面一个人在第几排再加1，终止条件f(1)=1
代码入下：

    public static Integer calculateCol(Integer n){
        if(n==1) return 1;
        return calculateCol(n-1)+1;
    }

2 比如目前有n级台阶，你可以一次走一阶台阶或一次走两阶台阶，走完n阶台阶有几种方法。仔细想一下，可以根据第一步的走法把所有走法分为两类，第一类是第一步走了1个台阶，另一类是第一步走了2个台阶。
推算如下：

微信截图_20210513230012.png

终止条件是 n=2或n=1。公式即为：f(n) =f(n-1)+f(n-2)
代码

    public static Integer calculateClimbe(Integer n){
        if(n==1) return 1;
        if(n==2) return 2;
        int value = calculateClimbe(n-1)+calculateClimbe(n-2);
        return value;
    }