再帰の考え方

最近，再帰の関数を書く機会がおおいのでまとめておく．

再帰には，次の2つが必要．

• 基底部：問題が解き終わったらどうするか？
• 再帰部：問題のうち，小さな部分を解決する

例えば，整数のリストの合計を再帰で求めるときは，

private static int head(List<Integer> list) {
   return list.get(0);
}
    
public static List<Integer> tail(List<Integer> list) {
   return list.subList(1, list.size());
}
    
public static int sum(List<Integer> list, int acc) {
   // 基底部：リストの要素がないとき，それまでの合計を返す
   if ( list.isEmpty() ) {
      return acc;
   }

   // 再帰部：それまでの合計値 acc に list の先頭要素を足す
   return sum(tail(list), acc + head(list));
}
    
public static int sum(List<Integer> list) {
   return sum(list, 0);
}