递归在程序语言中简单的理解是:方法自己调用自己
想要用递归必须知道两个条件:
技巧:在递归中常常是将问题切割成两个部分(1和整体的思想),这能够让我们快速找到递归表达式(规律)
int[] arrays = {2, 3, 4, 5, 1, 5, 2, 9, 5, 6, 8, 3, 2}
我们又可以运用1和整体的思想来找到规律
将数组第一个数->2与数组后面的数->{3, 4, 5, 1, 5, 2, 9, 5, 6, 8, 3, 2}进行切割,将数组后面的数看成是一个整体X={3, 4, 5, 1, 5, 2, 9, 5, 6, 8, 3, 2},那么我们就可以看成是第一个数和一个整体进行比较if(2>X) return 2 else(2<X) return X
而我们要做的就是找出这个整体的最大值与2进行比较。找出整体的最大值又是和我们的初始目的(找出最大值)是一样的,也就可以写成if( 2>findMax() )return 2 else return findMax()
递归出口,如果数组只有1个元素时,那么这个数组最大值就是它了。
/**
* @param arrays
* @param L 0
* @param R arrays.length-1
* @return
*/
int findMax(int[] arrays,int L,int R){
if(L==R){
return arrays[L];
}else{
int first = arrays[L];
int restMax = findMax(arrays,L+1,R);
if(first>restMax){
return first;
}else{
return restMax;
}
}
}
冒泡排序:俩俩交换,在第一趟排序中能够将最大值排到最后面,外层循环控制排序趟数,内层循环控制比较次数
以递归的思想来进行改造:
当第一趟排序后,我们可以将数组最后一位(R)和数组前面的数(L,R-1)进行切割,数组前面的数(L,R-1)看成是一个整体,这个整体又是和我们的初始目的(找出最大值,与当前趟数的末尾处交换)是一样的
递归出口:当只有一个元素时,即不用比较了:L==R
/**
* @param arrays
* @param L 0
* @param R arrays.length-1
*/
void bubbleSort(int[] arrays,int L,int R){
int temp;
if(L==R){
return;
}
else{
for(int i=L;i<R;i++){
if(arrays[i]>arrays[i+1]){
temp = arrays[i];
arrays[i] = arrays[i+1];
arrays[i+1] = temp;
}
}
}
bubbleSort(arrays,L,R-1);
}
暂时举两个例子,后面继续补充