資料結構之遞歸實作

1. 概念解釋：

程式調用自身的程式設計技巧稱為遞歸（ recursion）。遞歸做為一種算法在程式設計語言中廣泛應用。 一個過程或函數在其定義或說明中有直接或間接調用自身的一種方法，它通常把一個大型複雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解，遞歸政策隻需少量的程式就可描述出解題過程所需要的多次重複計算，大大地減少了程式的代碼量。遞歸的能力在于用有限的語句來定義對象的無限集合。

2. 遞歸條件

邊界條件 
遞歸前進段 
遞歸傳回段 
當邊界條件不滿足時，遞歸前進；當邊界條件滿足時，遞歸傳回。
           

3. 執行個體講解

1） 1，1，2，3，5，8… 斐波拉契數列

* ,,,,,,
 * 規律後一個數是前兩個數的和 n>=
 * @param n
 * @return
 */
public static long getFibonacciNumber(long n) throws Exception {
    if(n <= ){
        throw new Exception("數字不合法");
    }
    if(n == ){
        return ;
    }else if(n == ){
        return ;
    }
    return getFibonacciNumber(n-) + getFibonacciNumber(n- );
}
           

2） 1, 3, 6, 10, 15, 21…

/**
 * 1 3 6 10 15
 * 規律是後一個數等于第n個數n+它的前一個數的和，當n > 1時候
 * @param n
 * @return
 */
 public static int getTriangleNumber(int n){
    if(n <= ){
        return -;
    }else if(n == ){
        return ;
    }else{
        return n + getTriangleNumber(n - );
    }
 }
           

3） 漢諾塔問題

古代有一個梵塔，塔内有三個座A、B、C，A座上有64個盤子，盤子大小不等，大的在下，小的在上。有一個和尚想把這64個盤子從A座移到C座，但每次隻能允許移動一個盤子，并且在移動過程中，3個座上的盤子始終保持大盤在下，小盤在上。在移動過程中可以利用B座。

/**
 *
 * @param n 移動盤子數
 * @param from 起始塔座
 * @param mid  中間塔座
 * @param to   目标塔座
 */
public static void moveDish(int n,String from,String mid,String to){

    if(n == ){
        System.out.println("盤子1從"+from+"塔座移動到"+to+"塔座");
    }else{
        moveDish(n - ,from,to,mid);
        System.out.println("盤子"+ n +",從"+from+"塔座移動到" + to + "塔座");
        moveDish(n-,mid,from,to);
    }
}
           

4） 數組求和 比如 arr[] = [2,6,8];

private int sum(int[] arr,int l){
    if(l == arr.length)
        return ;
    return arr[l] + sum(arr,l+);
}
           

5） 删除連結清單中等于給定值 val 的所有節點。

示例:

輸入: 1->2->6->3->4->5->6, val = 6
輸出: 1->2->3->4->5
           

遞歸方式實作

public ListNode removeElements3(ListNode head, int val) {
    if(head == null)
        return null;
    //1->2->3->4
    head.next = removeElements3(head.next, val);
    return head.val == val ? head.next : head;
}

 帶虛拟頭節點方式實作

public ListNode removeElements2(ListNode head, int val) {

    //建構一個虛拟頭結點
    ListNode dummyHead = new ListNode(-);
    dummyHead.next = head;
    //1->2->3->4
    ListNode cur = dummyHead;
    while (cur.next != null){
        if(cur.next.val == val){
            ListNode delNode = cur.next;
            cur.next = delNode.next;
            delNode.next = null;
        }else{
            cur = cur.next;
        }
    }
    //這裡注意需要傳回dummyHead.next
    return dummyHead.next;
}

 不帶虛拟頭節點方式實作

public ListNode removeElements(ListNode head, int val) {

    while(head != null && head.val == val){
        head = head.next;
    }

    //1->2->3->4
    ListNode cur = head;
    while (cur != null && cur.next != null){
        if(cur.next.val == val){
            ListNode delNode = cur.next;
            cur.next = delNode.next;
            delNode.next = null;
        }else{
            cur = cur.next;
        }
    }

    return head;
}
           

4.聯系方式

QQ:1509815887