數(shù)學歸納法摇展，用于證明斷言對所有自然數(shù)成立

• 證明對于N=1成立
• 證明N>1時：如果對于N-1成立熊痴，那么對于N成立

如何證明遞歸函數(shù)正確執(zhí)行

• 數(shù)學歸納法中的數(shù)學徘铝、自然語言 <==> 程序語言

遞歸控制

• 嚴格定義遞歸函數(shù)作用携冤，包括參數(shù)盆繁，返回值，Side-effect
• 先一般，后特殊
• 每次調(diào)用必須縮小問題規(guī)模（如果不這樣就成了死循環(huán)）
• 每次問題規(guī)脑派矗縮小程度必須為1

例一：鏈表創(chuàng)建

public class Node {

    private final int value;

    private Node next;

    //構造時將next默認為空
    public Node(int value) {
        this.value = value;
        this.next = null;
    }

    public int getValue() {
        return value;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }

    //打印鏈表
    public static void printLinkedList(Node head){
        while(head != null){
            System.out.print(head.getValue());
            System.out.print(" ");
            head = head.getNext();
        }
        System.out.println();
    }
}

public class LinkedListCreator {

    /**
     * Creates a linked list.遞歸
     * @param data the data to create the list
     * @return head of the linked list.The returned linked list
     * ends with last node with getNext() == null
     */
    public Node createLinkedList(List<Integer> data){
        if(data.isEmpty()){
            return null;
        }
        Node firstNode = new Node(data.get(0));
        firstNode.setNext(createLinkedList(data.subList(1,data.size())));
        return firstNode;
    }


    //測試創(chuàng)建鏈表
    public static void main(String[] args) {
        LinkedListCreator creator = new LinkedListCreator();
        Node.printLinkedList(creator.createLinkedList(new ArrayList<>()));
        Node.printLinkedList(creator.createLinkedList(Arrays.asList(1)));
        Node.printLinkedList(creator.createLinkedList(Arrays.asList(1,2,3,4,5)));

    }
}

  /**
     * 循環(huán)創(chuàng)建鏈表
     * @param data
     * @return
     */
    public Node createLinkedList2(List<Integer> data){
        if(data.isEmpty()){
            return null;
        }
        Node firstNode = new Node(data.get(0));
        //循環(huán)創(chuàng)建鏈表
        Node curNode = firstNode;
        for(int i=1;i<data.size();i++){
            Node nextNode = new Node(data.get(i));
            curNode.setNext(nextNode);
            curNode = nextNode;
        }
        return firstNode;
    }

例二：鏈表反轉(zhuǎn)

public class LinkedListReverser {

    /**
     * Reaverses a linked list. 遞歸
     * @param head the linked list to reverse
     * @return head of the reversed linked list
     */
    Node reverseLinkedList(Node head){
        //size == 0 size == 1
        if(head == null || head.getNext() == null){
            return head;
        }

        Node newHead = reverseLinkedList(head.getNext());
        head.getNext().setNext(head);
        head.setNext(null);
        return newHead;
    }

    public static void main(String[] args) {
        LinkedListCreator creator = new LinkedListCreator();
        LinkedListReverser reverser = new LinkedListReverser();
        Node.printLinkedList(reverser.reverseLinkedList(creator.createLinkedList(new ArrayList<>())));
        Node.printLinkedList(reverser.reverseLinkedList(creator.createLinkedList(Arrays.asList(1))));
        Node.printLinkedList(reverser.reverseLinkedList(creator.createLinkedList(Arrays.asList(1,2,3,4,5))));

    }
}

    /**
     * 循環(huán)反轉(zhuǎn)鏈表
     * @param head
     * @return
     */
    Node reverseLinkedList2(Node head){
        Node newHead = null;
        Node curHead = head;
        while(curHead != null){
          Node next = curHead.getNext();
          curHead.setNext(newHead);
          newHead = curHead;
          curHead = next;
        }
        return newHead;
    }

例三：列出所有組合

combinations([1,2,3,4],2)
要點：多個參數(shù)的初始值

public class Combinations {

    /**
     * Generates all combinations and output them,
     * selecting n elements from data.
     * @param data
     * @param n
     */
    public void combinations(List<Integer> selected,List<Integer> data, int n){
        //initial value for recursion
        //how to select elements
        //how to output

        if(n ==0 ){
            //output all selected elements
            for(Integer i: selected){
                System.out.print(i);
                System.out.print(" ");
            }
            System.out.println();
            return ;
        }
        if(data.isEmpty()){
            return ;
        }
        // select element 0
        selected.add(data.get(0));
        combinations(selected, data.subList(1,data.size()),n-1);
        // un-select element 0
        selected.remove(selected.size() - 1);
        combinations(selected, data.subList(1,data.size()),n);

    }

    public static void main(String[] args) {
        Combinations comb = new Combinations();
        comb.combinations(new ArrayList<>(),Arrays.asList(1,2,3,4),2);
        System.out.println("=========================");
        comb.combinations(new ArrayList<>(),new ArrayList<>(),0);
        System.out.println("=========================");
        comb.combinations(new ArrayList<>(),new ArrayList<>(),2);
        System.out.println("=========================");
        comb.combinations(new ArrayList<>(),Arrays.asList(1,2,3,4),1);
        System.out.println("=========================");
        comb.combinations(new ArrayList<>(),Arrays.asList(1,2,3,4),0);
        System.out.println("=========================");
    }

}

遞歸缺點：函數(shù)調(diào)用開銷大敬肚，可能會Stack Overflow!
不要嘗試遞歸->非遞歸

例四：鏈表刪除節(jié)點

public Node deleteIfEquals(Node head,int value){
        while(head!=null && head.getValue() == value){
            head = head.getNext();
        }
        Node prev = head;
        if(head == null){
            return null;
        }
        while(prev.getNext() != null){
            if(prev.getNext().getValue() == value){
                prev.setNext(prev.getNext().getNext());
            }else{
                prev = prev.getNext();
            }
        }
        return head;
    }

例： 二分查找

• 在有序數(shù)組中查找元素K,返回K所在下標
• binarySearch([1,2,10,15,100],15) == 3

   /**
     * 二分查找
     * @param arr 有序
     * @param k
     * @return
     */
    public int binarySearch(int[] arr,int k){

        int a = 0;
        int b = arr.length;
        //[a,b)
        while(a < b){
            //int m = (a + b) / 2;
            int m = a + (b - a) / 2;
            if(k < arr[m]){//a...(m-1)
                b = m;
            }else if(k > arr[m]){//(m+1)...b
                a = m + 1;
            }else{
                return m;
            }
        }
        return -1;
    }

二叉樹的遍歷

前序遍歷：ABDEGCF
中序遍歷：DBGEACF
后序遍歷：DGEBFCA

/**
 *  樹
 * @author WangCH
 * @create 2018-03-14 20:02
 */
public class TreeNode {

    private final char value;

    private TreeNode left;

    private TreeNode right;

    public TreeNode(char value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }

    public char getValue() {
        return value;
    }

    public TreeNode getLeft() {
        return left;
    }

    public void setLeft(TreeNode left) {
        this.left = left;
    }

    public TreeNode getRight() {
        return right;
    }

    public void setRight(TreeNode right) {
        this.right = right;
    }
}

/**
 * 手動創(chuàng)建二叉數(shù)
 * @author WangCH
 * @create 2018-03-14 20:03
 */
public class TreeCreator {

    public TreeNode createSampleTree(){
        TreeNode root = new TreeNode('A');
        root.setLeft(new TreeNode('B'));
        root.getLeft().setLeft(new TreeNode('D'));
        root.getLeft().setRight(new TreeNode('E'));
        root.getLeft().getRight().setLeft(new TreeNode('G'));
        root.setRight(new TreeNode('C'));
        root.getRight().setRight(new TreeNode('F'));
        return root;
    }
}

/**
 * @author WangCH
 * @create 2018-03-21 13:46
 */
public class TreeTraversal {

    /**
     * 前序遍歷二叉樹
     * @param root
     */
    public void preOrder(TreeNode root){
        if(root == null){
            return;
        }
        System.out.print(root.getValue());
        preOrder(root.getLeft());
        preOrder(root.getRight());
    }

    /**
     * 中序遍歷
     * @param root
     */
    public void inOrder(TreeNode root){
        if(root == null){
            return;
        }
        inOrder(root.getLeft());
        System.out.print(root.getValue());
        inOrder(root.getRight());
    }

    /**
     * 后序遍歷
     * @param root
     */
    public void postOrder(TreeNode root){
        if(root == null){
            return;
        }
        postOrder(root.getLeft());
        postOrder(root.getRight());
        System.out.print(root.getValue());
    }

    public static void main(String[] args) {
        TreeCreator creator = new TreeCreator();
        TreeNode sampleTree= creator.createSampleTree();

        TreeTraversal treeTraversal = new TreeTraversal();
        System.out.print("前序遍歷：");
        treeTraversal.preOrder(sampleTree);
        System.out.println();
        System.out.print("中序遍歷：");
        treeTraversal.inOrder(sampleTree);
        System.out.println();
        System.out.print("后序遍歷：");
        treeTraversal.postOrder(sampleTree);
        System.out.println();
    }
}