数据结构基础-递归和循环技巧

为什么要用递归

递归是从数学领域的数学归纳法借鉴过来的一种技术。递归代码通常比迭代代码更加简洁易懂。当任务能够被相似的子任务定义时，采用递归处理十分有效。二分排序和遍历等问题往往有简洁的递归解决方案。

递归函数的格式

if (判断是否是基础情况) {
    return 该基础情况下的函数的值
} else if (判断是否为另一种基础情况) {
    return 该基础情况下的函数的值
    .
    .
    .
} else return (递归调用)

eg: 阶乘为例
n!=1 n = 0
n! = n * (n - 1)! n > 0

int fact(int n) {
    if (n == 1) return 1;
    else if (n == 0) return 1;
    else return n * fact(n-1);
}

递归和内存

每次递归调用都会在内存中生成一个新的函数副本。分析上面的阶乘函数：

recurse.png

每一次调用都会在程序运行的栈内存上创建一个函数副本，但是栈内存是有限的，当递归次数达到一个阈值的时候就会造成耗尽内存，栈溢出错误。

• 递归控制

1. 严格定义递归函数的作用，包括函数、返回值，side-effect
2. 先一般，后特殊
3. 每次调用必须缩小问题规模
4. 每次问题规模缩小程度必须为1

eg:创建链表

public Node createLinkedList(List<Integer> data){
    //最后考虑特殊情况
    if(data.isEmpty()){
        retrun null;
    }
    //先考虑一般情况，第一个成立，然后n-1个成立
    Node firstNode = new Node(data(0));
    Node headOfSublist = createLinkedList(data.subList(1,data.size()));
    firstNode.setNext(headOfSublist);
    return firstNode;
}

eg:反转链表

public Node reverseList(Node head){
    //最后思考的特殊情况
    if(head == null || head.getNext() == null){
        return head;
    }
    //一般情况 假如他可以反转链表得到出去第一个的剩下反转
    Node newHead = reverseList(head.getNext());
    head.getNext().setNext(head);
    head.setNext(null);
    return newHead;
}

回溯

回溯是一种采用分治策略进行穷举搜索的方法。（有时候求解一个问题最好的方法就是尝试所有的可能性）

• 二进制串
• 生成k进制串
• 背包问题
• 图的着色问题

eg:从一个数组中列出取出n个元素的所有的组合

首先分解问题，选第一个元素，然后再剩下的数组中选n-1个；不选第一个元素，然后从剩下的数组中选n个。

public void combinations(List<Integer> selected, List<Integer> data, int n){
    if(n == 0){
        for(Integer i : seleted){
            System.out.print(i+"");
        }
        return;
    }
    if(data.isEmpty()){
        return;
    }
    //selected first element
    seleted.add(data.get(0));
    combinations(selected, data.sublist(1,data.size()));
    
    //unselect first element
    selected.remove(selected.size() - 1);
    combinations(selected, data.sublist(1, data.size()), n);
}

• 循环控制

1. 定义循环不定式，并在循环体每次结束后保持循环不变式
2. 先一般，后特殊
3. 每次必须向前推进循环不变式中涉及的变量值
4. 每次推进的规模必须为1

eg：依然是上面的链表反转的例子，用循环不定式实现

public Node reverseLinkedList(Node head){
    Node newHead = null;
    Node curHead = head;
    while(curHead != null) {
        Node next = curHead.getNext();
        curHead.setNext(newHead);
        newHead = curHead;
        curHead = next;
    }
    return newHead;
}

eg:链表中delete_if

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

保持并推进反转关系

• 边界控制
  eg:二分查找

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