在数学中,很多数学函数都是由一个公式来表达的,比如 f(x) = 100x; 这个公式可以让我们把长度米转换成长度厘米。 有了这个公式,在程序中敲出一行代码,写出一个函数(function)来计算实在是太简单方便了,就像这样。
int convert(int m){
return 100*m;
}
我们就写好了一个函数来进行米到厘米的单位换算。
但是有的时候,数学函数会以不太标准的形式来定义,比如这个函数,他满足 f(0)=0而且 f(x) = 2f(x-1)+x; 从这个函数定义我们可以得出 f(1)=1;f(2)=3;等等。当一个函数用他自己来定义时就称为这个函数是递归的。
通俗地讲,就是从前有个山,山里有个庙,庙里有个老和尚再给小和尚讲故事,讲的是:从前有个山,山里有个庙,庙里有个老和尚再给小和尚讲故事。。。。这就是递归。
好了说了这么多你们肯定还是一头雾水,现在来实践一下。
递归求阶乘
刚开始学编程的同学一定会写求阶乘的函数,使用for循环或者while循环都可以,但是递归却完全用不上这两个循环。
public static int factorial(int a){
if (a==0 || a==1){
return 1;
}
return a*factorial(a-1);
}
上面的代码就是递归求阶乘的方法,a是需要传入的参数,比如我们要求5的阶乘就传入5这样factorial函数最终的返回值为120;
分析这段代码,他的第3行到第五行处理了 基准情况(Base Case),在这个情况下,函数的值可以直接算出而不用求出递归。就像上文提到的函数f(x) = 2f(x-1)+x;如果没有f(0)=0这个事实在数学上没有意义一样。 再编程中,如果没有基准情况也是无意义的。第7行执行的是递归调用。
所以所,设计递归算法,需要包含以下两个基本法则:
1、基准情形(Base Case),必须总要有某些基准的清醒,在这个情形中,不执行递归就能求解。
2、不断推进(Making Progress),对于需要递归求解的情形,递归调用必须总能够朝着一个基准情形推进。这样的话,不断推进到基准情形,到达基准情形的时候递归才会推出,得到返回值。
n阶矩阵行列式的求解
有了刚在知识的铺垫,现在我们可以动手写一个程序来用递归计算n阶矩阵的行列式了。
首先来看下二阶矩阵的求法:
也就是说2×2矩阵的元素交叉相乘再想减即可求出行列式。
接下来是3阶矩阵:
3×3矩阵求解中,选择任意行或者列,在那一行/列中,移除那个元素所在的行和列比如选择a11,则移除第一行和第一列,这样矩阵就变成了2×2的,再按照刚才的方法求2×2矩阵的行列式即可。之后整个行或列的3个元素进行此类运算后相加就是3×3的行列式。
n x n矩阵:
n阶矩阵就和3阶矩阵求解的方法一样了,使用3×3求解的方法,比如4阶矩阵,将4阶消除成3阶,然后再变成2阶来算。但是矩阵每上升一个维度,计算量就会扩大很多。
知道了n阶矩阵行列式的计算思路后,就可以开始编写算法了。
首先是数据结构设计,我们需要设计一个矩阵类来提供便利,这个类有两个成员,一个二维数组,用来储存矩阵,一个整数,来储存矩阵的行数或列数(行列式必须是方矩阵才可以求解所以行列无所谓)。
以下是整个Matrix类的设计:
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类中有两个构造方法:传入整数a会初始化一个axa大小的空矩阵,传入一个二维数组的话即可根据二维初始化一个Matrix对象。
Matrix类中有一个方法比较特殊:addElement方法,通过不断调用这个函数即可向一个Matrix实例进行有顺序的负值,第一次调用则会更改第第一行第一列位置上的值,第二次调用则会更改第一行第二列上的值,以此类推。
接下来就是设计一个MatrixCalculator类的,这个类中的一个成员方法可以求出行列式,我命名他为getDet(); 在计算行列式的时候需要移除元素所在的行和列,生成一个减小了一个维度的矩阵,我们需要编写一个方法来完成这个操作,我命名他为removeRowAndCol();还有一个方法,由于相加的时候会产生符号的改变,所以需要写一个方法来计算矩阵中一个元素的cofactor,命名为getCofactor。
以下就是removeRowAndCol方法的代码:传入需要移除的行和列和一个Matrix对象,函数会返回消除了指定行和列的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方法:由于我的算法只会去遍历矩阵第一列来进行求解,所以得到Cofactor的代码就变得简单很多。
public static int getCofactor(int colNum){
if (colNum%2 == 0){
return 1;
}else {
return -1;
}
}
接下来就是核心的递归求解行列式的算法了,先理一下思路,递归算法的两个要素:基准情形,不断推进。
对于n阶矩阵什么是基准情形呢?就是矩阵被降为2×2维度的时候,直接返回交叉相乘的差即可,不断推进,如果是一个4阶矩阵,算法会先把4将为3×3矩阵,然后3×3再拆成3个2×2矩阵来达到基准情形来算出答案,就和我们手算行列式时用到的方法一样,手算时候也遵循这一算法。
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的矩阵,是不是很神奇,这就是递归的优势,把一个很庞大的问题转化为规模缩小了的同类问题的子问题来求解。n阶矩阵最后被降为若干个2×2矩阵。
加上适当的输出语句,来求解一个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
但是有一个问题需要注意,就是这个算法的复杂度。
算法复杂度
这个算法的复杂度为O(n!), 这意味着他的运行速度很慢,随着问题规模的增长,时间会大幅度增长。在我的电脑上,计算3×3到7×7内规模的矩阵,电脑都可以秒算出来,但是如果是一个10×10的矩阵,电脑需要54秒钟,到了11×11时间将会变得更长,下图是这个算法随着问题规模增长对运行时产生影响的曲线。
可以看出7×7矩阵需要递归517次,到了10×10需要大约260万次递归运算才能得到结果。可见问题规模增长后时间的开销是十分巨大的。