public class RecursiveList {

	private Node first;

	public RecursiveList() {
		first = null;
	}

	public void clear() {
		first = null;
	}

	public void addLast(int value) {
		if (first == null)
			first = new Node(value, null);
		else
			addLast(first).next = new Node(value, null);
	}

	private Node addLast(Node current) {
		if (current.next == null)
			return current;
		else
			return addLast(current.next);
	}

	public boolean find(int info) {
		if (first == null)
			return false;
		else
			return find(first, info);
	}

	private boolean find(Node current, int value) {
		if (current.data == value)
			return true;
		else if (current.next == null)
			return false;
		else
			return find(current.next, value);
	}

	public void printInOrder() {
		System.out.println(printInOrder(first));
	}

	private String printInOrder(Node current) {
		if (current == null)
			return "";
		else if (current.next == null)
			return "" + current.data;
		else {
			return current.data + " " + printInOrder(current.next);
		}
	}

	public void printInReverse() {
		System.out.println(printInReverse(first));
	}

	private String printInReverse(Node current) {
		if (current == null)
			return "";
		else if (current.next == null)
			return "" + current.data;
		else {
			return printInReverse(current.next) + " " + current.data;
		}
	}

	public void removeLastNode() {
		if (first.next == null)
			first = null;
		else
			removeLastNode(first);
	}

	private void removeLastNode(Node current) {
		if (current.next.next == null)
			current.next = null;
		else
			removeLastNode(current.next);
	}

	public int numberOfNodes() {
		if (first == null)
			return 0;
		else
			return numberOfNodes(first);
	}

	private int numberOfNodes(Node current) {
		if (current.next == null)
			return 1;
		else
			return numberOfNodes(current.next) + 1;
	}

	public int sumOfEvenNumbersInList() {
		if (first == null)
			return 0;
		else
			return sumOfEvenNumbersInList(first);
	}

	private int sumOfEvenNumbersInList(Node current) {
		if (current == null)
			return 0;
		else if (current.data % 2 == 0)
			return (int) (sumOfEvenNumbersInList(current.next) + current.data);
		else
			return sumOfEvenNumbersInList(current.next);
	}

	public int numberOfOccurrences(int info) {
		if (first == null)
			return 0;
		else
			return numberOfOccurrences(first, info);
	}

	private int numberOfOccurrences(Node current, int value) {
		if (current == null)
			return 0;
		else if (current.data == value)
			return numberOfOccurrences(current.next, value) + 1;
		else
			return numberOfOccurrences(current.next, value);
	}

	public String toString() {
		if (first == null)
			return "";
		else
			return printInOrder(first);
	}

	public static void main(String[] args) {
		/* Test Code */
		RecursiveList TestList = new RecursiveList();
		TestList.addLast(2);
		TestList.clear();
		TestList.addLast(-1);
		TestList.addLast(42);
		TestList.addLast(1024);
		if (TestList.find(42))
			System.out.println("42 was found");
		if (!TestList.find(88))
			System.out.println("88 was NOT found");
		TestList.printInOrder();
		TestList.printInReverse();
		TestList.removeLastNode();
		TestList.printInOrder();
		if (!TestList.find(1024))
			System.out.println("1024 was removed");
		System.out.println("The number of nodes is: "
				+ TestList.numberOfNodes());
		TestList.addLast(6);
		TestList.addLast(6);
		TestList.addLast(6);
		System.out.println("The sum of even numbers is: "
				+ TestList.sumOfEvenNumbersInList());
		System.out.println("Six occurs " + TestList.numberOfOccurrences(6)
				+ " times");
		System.out.println(TestList);
	}

	private class Node {

		public int data;

		public Node next;

		public Node(int value, Node ptrToNext) {
			data = value;
			next = ptrToNext;
		}
	}

}