原理：分而治之(Divide and conquer)
Average case時間複雜度：O(n)
做法：
import java.util.ArrayList;
import java.util.List;
public class Test {
public static void main(String[] args) {
List<Integer> a = new ArrayList<>();
a.add(12);
a.add(33);
a.add(2);
a.add(84);
a.add(56);
a.add(5);
int lo = 0, hi = a.size()-1;
int sum = sum(a, lo, hi);
System.out.println(sum);
}
// 陣列求和：二分遞迴
public static int sum(List<Integer> a, int lo, int hi) {
if (lo == hi) return a.get(lo);// index相同，回傳其中一個值就可
// 將求和範圍切成兩半，效率比較快：先得出mid
int mid = (lo+hi) / 2;// 除以2
return sum(a, lo, mid) + sum(a,mid+1, hi);// 合併
}
}
如有敘述錯誤，還請不吝嗇留言指教，thanks!
