《程式設計簡介(Java) ·10.3遞歸思想》
以兩種方式的人：男人和女人；算法是兩種：遞歸疊代/通知；
遞歸方法用自己的較簡單的情形定義自己。
在數學和計算機科學中，遞歸是一種思路和政策，能夠用于術語的定義(什麼是表達式)，問題的描寫叙述和問題求解。用于問題求解的遞歸稱為遞歸法。
有一個故事。實體學家計算10！時會說。“看，它等于1*2*～*10，即3628800”；數學家則說：“哦。10的階乘，它等于10乘以9。”。
遞歸算法“輕率地”覺得自己的較簡單的情形是已知的。既然fact(n-1)是已知的，因而fact(n) 可求。
這樣“輕率”對了解遞歸概念至關重要。遞歸法不直接解決這個問題，而是将問題變成一個趨向遞歸出口的問題。使用遞歸方法須要存在一個基準情形，以避免無限循環(狗追自己的尾巴)。
大多數情況下，疊代法和遞歸法可以互相轉化。
使用遞歸法有2條實踐準則：
1、設計優先。在不論什麼情況下都能夠採用遞歸法。簡潔而清晰的程式設計優先。某些問題，比如那些須要後退的問題(如找出迷宮的出路、對樹的一些操作)。假設不採用遞歸則非常難解決。
2、效率平衡。
假設遞歸調用中出現反複性工作，改用循環。對于一般的數值計算，遞歸法通常不合适。
Java遞歸方法是通過方法調用棧實作的。在BlueJ中設定斷點執行factorial (5)，将顯示方法調用情況。
它隻“輕率地覺得”factorial (4)已知，依此類推。
到factorial (5)，眼下沒有進行任一乘法計算。方法調用棧中有6個棧幀，頂層将計算factorial (0)。遞歸的方法的兩個階段是遞推和回歸。
比如使用遞歸式sum(n) =n + sum(n-1)，yqj2065看見過一個趣題。
兩者有差别嗎？【注：在Java7時sum1(6000)StackOverflowError，Java8到大約13000才溢出。原因不明。】
漢諾塔問題(Hanoi Tower problem)：有三根杆子A、B、C，A杆上串有上小下大若幹碟子。
每次移動一塊碟子。在確定小碟子僅僅能疊在大碟子上面的條件下，利用B過渡，請把全部碟子從A杆移到C杆上。
對于具有遞歸思維的人。再多的碟子，也隻是是兩部分：上面的n-1個碟子被看成粘在一起的小碟子，而以下是一個大碟子。漢諾塔問題的遞歸算法：
結束條件： A杆上僅僅有一個碟子。将它移到C。
遞歸式：
1、将上面的n-1個碟子從出發地A移到中轉站B；
2、将第n個碟子移到目的地C；
3、将n-1個碟子從中轉站B移到目的地C。
hanoi(‘A’, ‘B’, ‘C’, 3)的輸出：
第1步: A→C
第2步: A→B
第3步: C→B
第4步: A→C
第5步: B→A
第6步: B→C
第7步: A→C
漢諾塔問題的疊代算法比較複雜，代碼庫中有參考實作。
練習：
1.Given a non-negative int n, return the sum of its digits recursively (no loops). Note that mod (%) by 10 yields the rightmost digit (126 % 10 is 6), while divide (/) by 10 removes the rightmost digit (126 / 10 is 12).
sumDigits(126) → 9
sumDigits(49) → 13
sumDigits(12) → 3
類似的： 遞歸求一個非負int包括的5的個數。
2.小朋友排排坐，單号伸出2手指，雙号伸出3手指，遞歸求n個小朋友時手指的總數。
sum(0) → 0
sum(1) → 2
sum(2) → 5
版權聲明：本文部落客原創文章，部落格，未經同意不得轉載。
本文轉自mfrbuaa部落格園部落格，原文連結：http://www.cnblogs.com/mfrbuaa/p/4869075.html，如需轉載請自行聯系原作者