10.3.1 遞歸的概念
在數學和計算機科學中，遞歸是一種思路和政策，可以用于術語的定義(什麼是表達式)，問題的描述和問題求解。
作為一種思路和政策，遞歸與分而治之(divide-and-conquer)互為因果。遞歸
- 可以用于術語的定義(如什麼是表達式)，
- 可以用于問題的描述（數學中的分段函數），
- 可以用于問題求解(程式設計中的遞歸調用)。稱為遞歸算法，簡稱遞歸法，後面直接叫遞歸。
遞歸是指用自己的較簡單的情形定義自己。有一個故事。實體學家計算10！時會說，“看，它等于1*2*～*10，即3628800”；數學家則說：“哦，10的階乘，它等于10乘以9！”。
遞歸算法“輕率地”認為自己的較簡單的情形是已知的。既然fact(n-1)是已知的，因而fact(n) 可求。這樣“輕率”對了解遞歸概念至關重要。遞歸法不直接解決問題，而是将問題變成一個趨向遞歸出口的問題。使用遞歸方法需要存在一個基準情形，以避免無限循環(狗追自己的尾巴)。
package algorithm.recursion;
public class RecursionDemo{
/**
* 遞歸求Fibonacci級數的第n個元素，n基于1的自然數。
*/
public static int fibonacc(int n){
if(n<=1) return n;//base case
else return fibonacc(n-1)+fibonacc(n-2);
}
/**
* 疊代求Fibonacci級數的第n個元素，n基于1的自然數。
*/
public static int fibonacc1(int n){
int first , second ,result ;
first =second=result= 1;
for(int i=3;i<=n ;i++){
result = first + second;
first = second;
second =result;
}
return result;
}
}
大多數情況下，疊代法和遞歸法能夠互相轉化。
使用遞歸法有2條實踐準則：
1、設計優先。在任何情況下都可以采用遞歸法，簡潔而清晰的程式設計優先。某些問題，例如那些需要後退的問題(如找出迷宮的出路、對樹的一些操作)，如果不采用遞歸則很難解決。
2、 效率平衡。如果遞歸調用中出現重複性工作，改用循環。對于一般的數值計算，遞歸法通常不合适。
Java遞歸方法是通過方法調用棧實作的。在BlueJ中設定斷點運作factorial (5)，将顯示方法調用情況。它僅僅“輕率地認為”factorial (4)已知，依此類推。到factorial (5)，目前沒有進行任一乘法計算。方法調用棧中有6個棧幀，頂層将計算factorial (0)。遞歸的方法的兩個階段是遞推和回歸。
例如使用遞歸式sum(n) =n + sum(n-1)，yqj2065看見過一個趣題。
static long sum1(long a) {
return (a == 1)? 1:(a + sum1(a - 1));
}
static long sum2(long a) {
return (a == 1)? 1:(sum2(a - 1) + a);
}
兩者有差別嗎？【注：在Java7時sum1(6000)StackOverflowError，Java8到大約13000才溢出。 原因不明。】
《程式設計導論（Java）·10.3.2 案例：漢諾塔問題》
練習：
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
