递归

递归在程序语言中简单的理解是:方法自己调用自己

想要用递归必须知道两个条件:

  • 递归出口(终止递归的条件)
  • 递归表达式(规律)

技巧:在递归中常常是将问题切割成两个部分(1和整体的思想),这能够让我们快速找到递归表达式(规律)

求数组最大的值

int[] arrays = {2, 3, 4, 5, 1, 5, 2, 9, 5, 6, 8, 3, 2}

我们又可以运用1和整体的思想来找到规律

  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. 而我们要做的就是找出这个整体的最大值与2进行比较。找出整体的最大值又是和我们的初始目的(找出最大值)是一样的,也就可以写成if( 2>findMax() )return 2 else return findMax()

  3. 递归出口,如果数组只有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;
            }
        }
    }

冒泡排序的递归实现

冒泡排序:俩俩交换,在第一趟排序中能够将最大值排到最后面,外层循环控制排序趟数,内层循环控制比较次数

以递归的思想来进行改造:

  1. 当第一趟排序后,我们可以将数组最后一位(R)和数组前面的数(L,R-1)进行切割,数组前面的数(L,R-1)看成是一个整体,这个整体又是和我们的初始目的(找出最大值,与当前趟数的末尾处交换)是一样的

  2. 递归出口:当只有一个元素时,即不用比较了: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);
    }

暂时举两个例子,后面继续补充


书籍推荐