使用遞歸時需要滿足的條件

1 解決該問題需要分解成幾個子問題
2 分解后的子問題的解決思路除了數(shù)據(jù)規(guī)模不同，求解思路完全一樣。
3 將問題分解成子問題，子問題又可以分解成子子問題并且要存在終止條件。

舉例：

1 去電影院看電影，如果你不知道自己目前所處第幾排，你可以詢問前面一排是第幾排，前面一個還不知道自己是第幾排，可以繼續(xù)往前問，一直問道第一排。讓后第一排的人告訴問他的人，最終知道你所處的第幾排。公式為 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階臺階有幾種方法。仔細想一下，可以根據(jù)第一步的走法把所有走法分為兩類，第一類是第一步走了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;
    }