数学归纳法，用于证明断言对所有自然数成立

• 证明对于N=1成立
• 证明N>1时：如果对于N-1成立，那么对于N成立

如何证明递归函数正确执行

• 数学归纳法中的数学、自然语言 <==> 程序语言

递归控制

• 严格定义递归函数作用，包括参数，返回值，Side-effect
• 先一般，后特殊
• 每次调用必须缩小问题规模（如果不这样就成了死循环）
• 每次问题规模缩小程度必须为1

例一：链表创建

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;
    }


    //测试创建链表
    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)));

    }
}

  /**
     * 循环创建链表
     * @param data
     * @return
     */
    public Node createLinkedList2(List<Integer> data){
        if(data.isEmpty()){
            return null;
        }
        Node firstNode = new Node(data.get(0));
        //循环创建链表
        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;
    }

例二：链表反转

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))));

    }
}

    /**
     * 循环反转链表
     * @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)
要点：多个参数的初始值

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("=========================");
    }

}

递归缺点：函数调用开销大，可能会Stack Overflow!
不要尝试递归->非递归

例四：链表删除节点

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;
    }

例： 二分查找

• 在有序数组中查找元素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;
    }
}

/**
 * 手动创建二叉数
 * @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();
    }
}