最近高等代數(shù)正好講到這里，此篇文章正好對所學(xué)知識做一個具體程序?qū)嵺`惕稻。

設(shè)計算法時使用遞歸的思想是一個程序員的基本素質(zhì)栋齿，遞歸可以把一個很龐大的問題轉(zhuǎn)化為規(guī)模縮小了的同類問題的子問題狡刘，通過這一思想享潜，我們編程時運用遞歸可以使用很少的代碼來處理很大的問題。這篇文章將會講到遞歸算法的運用嗅蔬。

在數(shù)學(xué)中剑按，很多數(shù)學(xué)函數(shù)都是由一個公式來表達(dá)的，比如 f(x) = 100x; 這個公式可以讓我們把長度米轉(zhuǎn)換成長度厘米澜术。 有了這個公式艺蝴，在程序中敲出一行代碼，寫出一個函數(shù)（function）來計算實在是太簡單方便了鸟废，就像這樣猜敢。

int convert(int m){
    return 100*m;
}

我們就寫好了一個函數(shù)來進(jìn)行米到厘米的單位換算。

但是有的時候盒延，數(shù)學(xué)函數(shù)會以不太標(biāo)準(zhǔn)的形式來定義缩擂，比如這個函數(shù)，他滿足 f(0)=0而且 f(x) = 2f(x-1)+x; 從這個函數(shù)定義我們可以得出 f(1)=1;f(2)=3;等等添寺。當(dāng)一個函數(shù)用他自己來定義時就稱為這個函數(shù)是遞歸的胯盯。

通俗地講，就是從前有個山计露，山里有個廟，廟里有個老和尚再給小和尚講故事票罐，講的是：從前有個山叉趣，山里有個廟，廟里有個老和尚再給小和尚講故事胶坠。君账。。沈善。這就是遞歸乡数。

好了說了這么多你們肯定還是一頭霧水椭蹄，現(xiàn)在來實踐一下。

遞歸求階乘

剛開始學(xué)編程的同學(xué)一定會寫求階乘的函數(shù)净赴，使用for循環(huán)或者while循環(huán)都可以绳矩，但是遞歸卻完全用不上這兩個循環(huán)。

public static int factorial(int a){
 
    if (a==0 || a==1){
        return 1;
    }
 
    return a*factorial(a-1);
}

上面的代碼就是遞歸求階乘的方法玖翅，a是需要傳入的參數(shù)翼馆，比如我們要求5的階乘就傳入5這樣factorial函數(shù)最終的返回值為120；

分析這段代碼金度，他的第3行到第五行處理了 基準(zhǔn)情況（Base Case）应媚，在這個情況下，函數(shù)的值可以直接算出而不用求出遞歸猜极。就像上文提到的函數(shù)f(x) = 2f(x-1)+x;如果沒有f(0)=0這個事實在數(shù)學(xué)上沒有意義一樣中姜。 再編程中，如果沒有基準(zhǔn)情況也是無意義的跟伏。第7行執(zhí)行的是遞歸調(diào)用丢胚。

所以所，設(shè)計遞歸算法受扳，需要包含以下兩個基本法則：

1携龟、基準(zhǔn)情形（Base Case），必須總要有某些基準(zhǔn)的清醒勘高，在這個情形中峡蟋，不執(zhí)行遞歸就能求解。

2相满、不斷推進(jìn)（Making Progress）层亿，對于需要遞歸求解的情形，遞歸調(diào)用必須總能夠朝著一個基準(zhǔn)情形推進(jìn)立美。這樣的話，不斷推進(jìn)到基準(zhǔn)情形方灾，到達(dá)基準(zhǔn)情形的時候遞歸才會推出建蹄，得到返回值。

n階矩陣行列式的求解

有了剛在知識的鋪墊裕偿，現(xiàn)在我們可以動手寫一個程序來用遞歸計算n階矩陣的行列式了洞慎。

首先來看下二階矩陣的求法：

也就是說2×2矩陣的元素交叉相乘再想減即可求出行列式。

接下來是3階矩陣：

3×3矩陣求解中嘿棘，選擇任意行或者列劲腿，在那一行/列中,移除那個元素所在的行和列比如選擇a11，則移除第一行和第一列鸟妙，這樣矩陣就變成了2×2的焦人，再按照剛才的方法求2×2矩陣的行列式即可挥吵。之后整個行或列的3個元素進(jìn)行此類運算后相加就是3×3的行列式。

n x n矩陣：

n階矩陣就和3階矩陣求解的方法一樣了花椭，使用3×3求解的方法忽匈，比如4階矩陣，將4階消除成3階矿辽，然后再變成2階來算丹允。但是矩陣每上升一個維度，計算量就會擴大很多袋倔。

知道了n階矩陣行列式的計算思路后雕蔽，就可以開始編寫算法了。

首先是數(shù)據(jù)結(jié)構(gòu)設(shè)計宾娜，我們需要設(shè)計一個矩陣類來提供便利萎羔，這個類有兩個成員，一個二維數(shù)組碳默，用來儲存矩陣贾陷，一個整數(shù)，來儲存矩陣的行數(shù)或列數(shù)（行列式必須是方矩陣才可以求解所以行列無所謂）嘱根。

以下是整個Matrix類的設(shè)計：

static class Matrix{
 
    private int rowNum=0;
 
    private int[][] array;
 
    //Constructor
    public Matrix(int rowNum){
        this.rowNum = rowNum;
        array = new int[rowNum][rowNum];
    }
 
    public Matrix(int[][] array){
        this.array = array;
        this.rowNum = array.length;
    }
 
    int counter = 0; //For add Element
 
    public void addElement(int a){
        array[(counter)/rowNum][counter%rowNum] = a;
        counter++;
    }
 
    //Print the instance itself
    public void printMat(){
        for (int i=0;i < rowNum ;i++){
            for (int j=0;j < rowNum ;j++){
                 System.out.print(array[i][j]+\t;);
            }
            System.out.println();
        }
    }
 
    //Setter and Getter
    public int getRowNum() {
        return rowNum;
    }
 
    public int[][] getArray() {
        return array;
    }
 
    public void setArray(int[][] array) {
        this.array = array;
    }
 
}

Matrix類中有兩個構(gòu)造方法：傳入整數(shù)a會初始化一個axa大小的空矩陣髓废，傳入一個二維數(shù)組的話即可根據(jù)二維初始化一個Matrix對象。

Matrix類中有一個方法比較特殊：addElement方法该抒，通過不斷調(diào)用這個函數(shù)即可向一個Matrix實例進(jìn)行有順序的負(fù)值慌洪，第一次調(diào)用則會更改第第一行第一列位置上的值，第二次調(diào)用則會更改第一行第二列上的值凑保，以此類推冈爹。

接下來就是設(shè)計一個MatrixCalculator類的，這個類中的一個成員方法可以求出行列式欧引，我命名他為getDet(); 在計算行列式的時候需要移除元素所在的行和列频伤，生成一個減小了一個維度的矩陣，我們需要編寫一個方法來完成這個操作芝此，我命名他為removeRowAndCol()憋肖；還有一個方法，由于相加的時候會產(chǎn)生符號的改變婚苹，所以需要寫一個方法來計算矩陣中一個元素的cofactor岸更，命名為getCofactor。

以下就是removeRowAndCol方法的代碼：傳入需要移除的行和列和一個Matrix對象膊升，函數(shù)會返回消除了指定行和列的Matrix對象怎炊。

public static Matrix removeRowAndCol(int row,int col,Matrix mat){
 
    int matRowNum = mat.getRowNum();
    int[][] arr = mat.getArray();
 
    Matrix matrix = new Matrix(matRowNum-1);
 
    for (int i = 0;i < matRowNum; i++){
        for (int j = 0 < matRowNum; j++){
                if (i!=row && j!=col) {
                    matrix.addElement(arr[i][j]);
                }
        }
    }
 
    matrix.printMat();
    return matrix;
 
}

以下是getCofactor方法：由于我的算法只會去遍歷矩陣第一列來進(jìn)行求解，所以得到Cofactor的代碼就變得簡單很多。

public static int getCofactor(int colNum){
    if (colNum%2 == 0){
        return 1;
    }else {
        return -1;
    }
}

接下來就是核心的遞歸求解行列式的算法了评肆，先理一下思路债查，遞歸算法的兩個要素：基準(zhǔn)情形，不斷推進(jìn)糟港。

對于n階矩陣什么是基準(zhǔn)情形呢攀操？就是矩陣被降為2×2維度的時候，直接返回交叉相乘的差即可秸抚，不斷推進(jìn)速和，如果是一個4階矩陣，算法會先把4將為3×3矩陣剥汤，然后3×3再拆成3個2×2矩陣來達(dá)到基準(zhǔn)情形來算出答案颠放，就和我們手算行列式時用到的方法一樣，手算時候也遵循這一算法吭敢。

public static int getDet(Matrix targetMatrix){
    //Base (Finally reduced to 2 x 2 Matrix)
    if (targetMatrix.rowNum == 2){
        int[][] arr = targetMatrix.getArray();
        // a*d - b*c
        return arr[0][0]*arr[1][1] - arr[0][1]*arr[1][0];
    }
 
    //MARK- Recursion: to reduce dimension
    int det = 0;
    int colNum = targetMatrix.rowNum;
    for (int i = 0; < colNum;i++){
        det+= (targetMatrix.getArray()[i][0])*getCofactor(i)*getDet(removeRowAndCol(i,0,targetMatrix));
    }
 
    return det;
}

只有不到20行代碼碰凶，但是卻可以解決nxn的矩陣，是不是很神奇鹿驼，這就是遞歸的優(yōu)勢欲低，把一個很龐大的問題轉(zhuǎn)化為規(guī)模縮小了的同類問題的子問題來求解畜晰。n階矩陣最后被降為若干個2×2矩陣砾莱。

加上適當(dāng)?shù)妮敵稣Z句，來求解一個3階矩陣行列式試一下：

2   1    2 
-1   5   21 
13 -1  -17

Element: 2
Cofactor: 1
Removing Row 0 Col 0
A 2 x 2 Matrix is initialized 
5 21 
-1 -17 
END State Reached
Det: -64

Element: -1
Cofactor: -1
Removing Row 1 Col 0
A 2 x 2 Matrix is initialized 
1 2 
-1 -17 
END State Reached
Det: -15

Element: 13
Cofactor: 1
Removing Row 2 Col 0
A 2 x 2 Matrix is initialized 
1 2 
5 21 
END State Reached
Det: 11
Result: 0

但是有一個問題需要注意凄鼻，就是這個算法的復(fù)雜度腊瑟。

算法復(fù)雜度

這個算法的復(fù)雜度為O(n!), 這意味著他的運行速度很慢，隨著問題規(guī)模的增長块蚌，時間會大幅度增長闰非。在我的電腦上，計算3×3到7×7內(nèi)規(guī)模的矩陣峭范，電腦都可以秒算出來财松，但是如果是一個10×10的矩陣，電腦需要54秒鐘虎敦，到了11×11時間將會變得更長游岳，下圖是這個算法隨著問題規(guī)模增長對運行時產(chǎn)生影響的曲線。

可以看出7×7矩陣需要遞歸517次其徙，到了10×10需要大約260萬次遞歸運算才能得到結(jié)果∨缁В可見問題規(guī)模增長后時間的開銷是十分巨大的唾那。

原文：http://miketech.it/recursion_algorithm/ 感謝此篇文章的作者！