ぶれいすさんのやつ、http://bleis-tift.hatenablog.com/entry/20120119/1326944722 　Javaで書いてみる

再帰わからん.java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.function.Function;

public class Recursive {

	/**
	 * listを集計する奴
	 * @param xs リスト
	 * @return 集計値
	 */
	public static int sum(List<Integer> xs) {
		if(xs.isEmpty()) {
			return 0;
		} else {
			Tuple<Integer, List<Integer>> y_ys = headTail(xs);
			return y_ys.head + sum(y_ys.tail);
		}
	}
	
	/**
	 * リストの長さはかるやつ
	 * @param xs List
	 * @return 長さ
	 */
	public static int length(List<Integer> xs) {
		if(xs.isEmpty()) {
			return 0;
		} else {
			Tuple<Integer, List<Integer>> y_ys = headTail(xs);
			return 1 + length(y_ys.tail);
		}
	}
	
	/**
	 * Listの中の最大値を返す
	 * @param xs List
	 * @return 最大値
	 */
	public static int max(List<Integer> xs) {
		if(xs.isEmpty()) {
			return 0;
		} else {
			Tuple<Integer, List<Integer>> y_ys = headTail(xs);
			int ret = max(y_ys.tail);
			return ret < y_ys.head ? y_ys.head : ret;
		}
	}
	
	
	/**
	 * 全部条件満たせばtrue、一個でもだめならfalse
	 * @param xs List
	 * @param pred 条件関数
	 * @return 判定結果
	 */
	public static boolean forall(List<Integer> xs, Function<Integer, Boolean> pred) {
		if(xs.isEmpty()) {
			return true;
		} else {
			Tuple<Integer, List<Integer>> y_ys = headTail(xs);
			return pred.apply(y_ys.head) && forall(y_ys.tail, pred);
		}
	}
	
	/**
	 * 条件にあう、最初のやつを返す
	 * @param xs List
	 * @param pred 条件
	 * @return 条件にあう最初のやつ
	 */
	public static int find(List<Integer> xs, Function<Integer, Boolean> pred) {
		if(xs.isEmpty()) {
			return 0;
		} else {
			Tuple<Integer, List<Integer>> y_ys = headTail(xs);
			return pred.apply(y_ys.head) ? y_ys.head : find(y_ys.tail, pred);
		}
	}
	
	/**
	 * n回要素とばすやつ
	 * @param xs List
	 * @param n 回数
	 * @return スキップしたList
	 */
	public static List<Integer> skip(List<Integer> xs, int n) {
		if(xs.isEmpty()) {
			return Collections.emptyList();
		}else if(n == 0) {
			return xs;
		} else {
			Tuple<Integer, List<Integer>> y_ys = headTail(xs);
			return skip(y_ys.tail, n - 1);
		}
	}
	
	/**
	 * Listの要素をアレするやつ
	 * @param xs List
	 * @param f アレ
	 * @return アレしたあとのList
	 */
	public static List<Integer> map(List<Integer> xs, Function<Integer, Integer> f) {
		if(xs.isEmpty()) {
			return Collections.emptyList();
		} else {
			Tuple<Integer, List<Integer>> x_xs = headTail(xs);
			return cons(f.apply(x_xs.head), map(x_xs.tail, f));
		}
	}
	
	/**
	 * Listの絞込
	 * @param xs List
	 * @param pred 絞込条件
	 * @return 絞り込んだList
	 */
	public static List<Integer> filter(List<Integer> xs, Function<Integer, Boolean> pred) {
		if(xs.isEmpty()) {
			return Collections.emptyList();
		} else {
			Tuple<Integer, List<Integer>> x_xs = headTail(xs);
			return pred.apply(x_xs.head) ? cons(x_xs.head, filter(x_xs.tail, pred)) : filter(x_xs.tail, pred);
		}
	}	
	
	
	/**
	 * Tupleクラス。というかPairだ
	 * @author yy yank
	 *
	 * @param <H> head
	 * @param <T> tail
	 */
	private static class Tuple<H, T> {
		H head;
		T tail;
		public Tuple(H head, T tail) {
			this.head = head;
			this.tail = tail;
		}
	}
	
	/**
	 * headTailメソッド。頭と尻尾に分ける
	 * @param xs Listの何か
	 * @return Tuple型のheadとtail
	 */
	private static <T> Tuple<T, List<T>> headTail(List<T> xs) {
		return xs.size() != 1 ? new Tuple<>(xs.get(0), xs.subList(1, xs.size())) : new Tuple<>(xs.get(0), Collections.emptyList());
	}
	
	/**
	 * cons。多分これで合ってるはず
	 * @param x 先頭
	 * @param xs コピー元
	 * @return 先頭 + コピー元を連結したリスト
	 */
	private static <T> List<T> cons(T x, List<T> xs) {
		List<T> res = new ArrayList<>();
	    res.add(x);
	    res.addAll(xs);
	    return res;
	}
	
	
}