递归(recursion)

如何设计递归算法

1. 确定递归公式
2. 确定边界条件

1. Fibonacci

public static int fibonacci(int n) {
    if(n == 0 || n == 1) {
        return n;
    } else {
        return fibonacci(n-1) + fibonacci(n-2);
    }
}

2. 快速排序（Quick Sort）

public static int partition(int[] a, int p, int q) {
    int pivot = a[q];
    int index = 0;
    for(int i = p; i < q; i++) {
        if(a[i] <= pivot) {         
            int temp = a[i];
            a[i] = a[index];
            a[index] = temp;
            index++;
        }
    }
    int temp = a[index];
    a[index] = pivot;
    a[q] = temp;
    
    return index;
}
public static void quickSort(int[]a, int p, int q) {
    if(p < q) {// 如果p大于等于r 那么就程序不执行  
        int mid = partition(a, p, q);
        quickSort(a, p, mid-1);
        quickSort(a, mid+1, q);
    }
}

3. 归并排序（Merge Sort）

public static void merge(int[] a, int left, int mid, int right) {
    int m = mid - left + 1;
    int n = right - mid;
    int[] leftArr = new int[m+1];
    int[] rightArr = new int[n+1];
    for(int i = 0; i < m; i++) {
        leftArr[i] = a[left+i];
    }
    for(int i = 0; i < n; i++) {
        rightArr[i] = a[mid+i+1];
    }
    leftArr[m] = Integer.MAX_VALUE;
    rightArr[n] = Integer.MAX_VALUE;
    int i = 0;
    int j = 0;
    for(int k = left; k <= right; k++) {
        if(leftArr[i] <= rightArr[j]) {
            a[k] = leftArr[i++];
        } else {
            a[k] = rightArr[j++];
        }
    }
}
public static void mergeSort(int[] a, int left, int right) {
    if(left < right) { //当left>=right 说明子数组最多只有一个元素，已经排好序了
        int mid = (left + right) / 2;
        mergeSort(a, left, mid);
        mergeSort(a, mid+1, right);
        merge(a, left, mid, right);
    }
}

4. 二分查找（Binary Search）

public static int binarySearch(int[] arr, int key, int left, int right) {
    if(left > right)
        return -1;
    int mid = (left + right) / 2;
    if(arr[mid] == key) {
        return mid;
    } else if(arr[mid] > key) {
        return binarySearch(arr, key, left, mid-1);
    } else {
        return binarySearch(arr, key, mid+1, right);
    }
}

5. 全排列

6. 欧几里得算法（辗转相除法）

/*
 * m >= n
 */
public static int gcd(int m, int n) {
    if(n == 0) {
        return m;
    } else {
        return gcd(n, m%n);
    }
}

7. 1加到n累加

public static int sum(int n) {
    if(n == 1)
        return 1;
    else 
        return n+sum(n-1);
}

8. 求数组中的最大值

public static int max(int[] a, int n) {
    if(n == 0)
        return a[0];
    else {
        if(a[n] > max(a, n-1)) {
            return a[n];
        } else {
            return max(a, n-1);
        }
    }
}

    public static int maximum(int[] a, int low, int high) {
        int delt = high - low + 1;
        if(delt == 1) {
            return a[low];
        } else if(delt == 2) {
            return a[low] > a[high]? a[low]: a[high];
        } else {
            int mid = (low + high) / 2;
            int left = maximum(a, low, mid);
            int right = maximum(a, mid+1, high);
            return left > right? left: right;
        }
    }

9. 八皇后