递归

一、递归的概念：

       递归可以理解为把责任推给别人，但是不能无限推下去，得会有一个基值情况，不会继续进行递归调用，否则就是庞氏骗局。

       递归因为必须要保存每次调用的栈，所以容易造成栈溢出，而尾递归不需要保存之前的栈，所以不会造成栈溢出，前提是编译器要对尾递归进行优化。由于java目前还没有对尾递归进行优化，所以递归和尾递归效率一样，但是c中对尾递归有优化。

package com.xwiam.algorithms.recursion;

public class Triangle {

    public static int recursive(int value) {
        if (value == 1) {
            return 1;
        } else {
            return value + recursive(value - 1);
        }
    }

    /**
     * 尾递归
     * @param value
     * @param tail
     * @return
     */
    public static int recursiveTail(int value, int tail) {
        if (value == 1) {
            return tail;
        } else {
            return recursiveTail(value - 1, value + tail);
        }
    }

    public static void main(String[] args) {
        int value = 20000;
        System.out.println(Triangle.recursive(value));
        System.out.println(Triangle.recursiveTail(value, 1));
    }

}

二、递归的应用实例

package com.xwiam.algorithms.recursion;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * 单词的全排列
 */
public class Anagram {

    private static char[] array = new char[100];
    private static int maxSize;
    private static int size;

    public static void doAnagram(int n) {
        if (n == 1) {
            return;
        } else {
            for (int i = 0;i < n;i++) {
                doAnagram(n - 1);
                if (n == 2) {
                    displayWord();
                }
                rotate(n);
            }
        }
    }

    private static void displayWord() {
        for (int i = 0;i < size;i++) {
            System.out.print(array[i]);
        }
        System.out.println();
    }

    public static void rotate(int n) {
        int i;
        int position = size - n;
        char temp = array[position];
        for (i = position + 1;i < size;i++) {
            array[i - 1] = array[i];
        }
        array[size - 1] = temp;

    }

    public static String getString() throws IOException{
        InputStreamReader reader = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(reader);
        return br.readLine();
    }

    public static void charSet(String str) {
        for (int i = 0;i < str.length();i++) {
            array[i] = str.charAt(i);
        }
    }

    public static void main(String[] args) throws IOException{
        String input = getString();
        size = input.length();
        charSet(input);
        doAnagram(size);
    }

}

三、汉诺塔问题

package com.xwiam.algorithms.recursion;

public class Tower {

    private static int disk;

    public static void doTower(int topN, char from, char inter, char to) {
        if (topN == 1) {
            System.out.println("Disk 1 from " + from + " to " + to);
        } else {
            doTower(topN -1,from, to, inter);
            System.out.println("Disk " + topN + " from " + from + " to " + to);
            doTower(topN -1,inter, from, to);
        }
    }

    public static void main(String[] args) {
        disk = 3;
        doTower(disk, 'A', 'B', 'C');
    }
}

四、归并排序

package com.xwiam.algorithms.recursion;

/**
 * 归并排序
 */
public class MergeSort {

    private int size;
    private long[] array;

    public MergeSort(int maxSize) {
        array = new long[maxSize];
    }

    public void insert(long value) {
        array[size++] = value;
    }

    public void display() {
        for (int i = 0;i < size;i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println(" ");
    }

    public void sort() {
        long[] workspace = new long[size];
        recursive(workspace, 0, size - 1);
    }

    private void recursive(long[] workspace, int lowBound, int highBound) {
        if (lowBound == highBound) {
            return;
        } else {
            int mid = (lowBound + highBound) / 2;
            recursive(workspace, lowBound, mid);
            recursive(workspace, mid + 1, highBound);
            merge(workspace, lowBound, mid + 1, highBound);
        }
    }

    private void merge(long[] workspace, int lowStart, int highStart, int highBound) {
        int tempLow = lowStart;
        int lowBound = highStart- 1;
        int j = 0;
        int n = highBound - lowStart + 1;
        while (lowStart <= lowBound && highStart <= highBound) {
            if (array[lowStart] < array[highStart]) {
                workspace[j++] = array[lowStart++];
            } else {
                workspace[j++] = array[highStart++];
            }
        }
        while (lowStart <= lowBound) {
            workspace[j++] = array[lowStart++];
        }
        while (highStart <= highBound) {
            workspace[j++] = array[highStart++];
        }
        for (j = 0;j < n;j++) {
            array[tempLow + j] = workspace[j];
        }
    }

    public static void main(String[] args) {
        MergeSort mergeSort = new MergeSort(100);
        mergeSort.insert(10);
        mergeSort.insert(60);
        mergeSort.insert(30);
        mergeSort.insert(20);
        mergeSort.insert(80);
        mergeSort.display();
        mergeSort.sort();
        mergeSort.display();
    }
}

归并排序的效率：

归并排序的运行时间（包括复制和比较的时间）是O(N*logN)，比简单排序快很多，但是归并排序需要两倍的内存空间，如果有足够的空间，归并排序是一个很好的选择。