public class Toolbox {
	
	/* evenSum: */
    
    public static int evenSum(int n) {
    	// Zahl <n> gerade machen, falls ungerade (Bsp.: -5 -> -4, 7 -> 6, 2 -> 2):
    	if (!isEven(n)) {  // nicht gerade (! entspricht ==false)
    		if (n < 0)
    			n += 1;  // nächstgrößere, falls negativ
    		else
    			n -= 1;  // nächstkleinere, falls positiv
    	}
    	
    	// Ergebnis der Hilfsmethode zurückgeben:
    	return evenSumHelper(n);
    }

    /** 
     * Prüft rekursiv, ob eine Zahl gerade (true) ist oder nicht (false). 
     */
    private static boolean isEven(int n) {
    	// Rekursionsanker:
        if (n == 1 || n == -1)
            return false;
        else if (n == 0)
            return true;
        
        // Rekursive Berechnung:
        if (n > 0)
            return isEven(n-2);
        else
            return isEven(n+2);
    }
    
    /** 
     * Hilfsfunktion, welche das tut, was evenSum tun soll, als Parameter 
     * aber einen geraden Wert erwartet. 
     */
    private static int evenSumHelper(int n) {    	
        if (n < 0)  // -2, -4, -6, ...
            return n + evenSum(n+2);
        else if (n > 0)  // 2, 4, 6, ...
            return n + evenSum(n-2);
        else // 0
            return 0;
    }
    
    
    /* multiplication: */    

    public static int multiplication(int x, int y) {
    	// Rekursionsanker:
        if (y == 0 || x == 0)
            return 0;
        
        // Rekursionsvorschrift:
        if (y > 0)
            return x + multiplication(x, y-1);
        else  // y negativ -> x negativ machen
            return -x + multiplication(x, y+1);
    }
    
    
    /* reverse: */

    public static void reverse(int[] m) {
        reverse(m, 0);  // rufe Hilfsmethode mit passenden Parametern auf
    }
    
    /** 
     * Vertauscht das Element am Index <pos> (beginnend beim ersten Element)
     * mit dem Element am Index <pos> rückwärts gezählt und fährt rekursiv
     * mit allen dazwischenliegenden Elementen fort.
     * 
     * Beispiel: reverse([1,2,3,4,5], 0) = 
     *           reverse([5,2,3,4,1], 1) = 
     *           reverse([5,4,3,2,1], 2) = 
     *           [5,4,3,2,1] 
     */
    private static void reverse(int[] m, int pos) {
    	// Rekursionsanker: Mitte erreicht
        if (pos >= m.length/2)
            return;
        
        // Tausche am Index <pos>:
        int tmp = m[pos];  // Index pos von vorne
        m[pos] = m[m.length-pos-1];  // Index pos von hinten
        m[m.length-pos-1] = tmp;
        
        // Rekursiv mit nächster Position fortfahren:
        reverse(m, pos+1);
    }

    
    /* numberOfOddIntegers: */
    
    public static int numberOfOddIntegers(int[] m) {
        return numberOfOddIntegers(m, 0);  // rufe Hilfsmethode auf
    }
    
    /**
     * Hilfsmethode, welche als Parameter den Index übergeben bekommt, ab dem
     * die Anzahl ungerader Zahlen bestimmen soll. Dieser Index wird wie in
     * einer Schleife pro rekursivem Aufruf um 1 erhöht. Es wird dann jeweils
     * (pro rekursivem Aufruf) nur der Eintrag (im Array) an der Stelle <pos> 
     * betrachtet. Um alle darauffolgenden Zahlen kümmert sich der rekursive
     * Aufruf.
     */
    private static int numberOfOddIntegers(int[] m, int pos) {
    	// Rekursionsanker (alle Elemente aus m behandelt):
        if (pos >= m.length)
            return 0;
        
        // Prüfe, ob Element an der aktuellen Position ungerade ist. Wenn ja,
        // dann addiere 1 zum rekursiven Aufruf mit dem nächsten Index:
        int isOdd = 0;
        if (isEven(m[pos]))
            isOdd = 1;
        return isOdd + numberOfOddIntegers(m, pos+1);
    }
    
    
    /* filterOdd: */

    public static int[] filterOdd(int[] m) {
    	// Erzeuge ein Array passender Größe:
    	int length = numberOfOddIntegers(m);
    	int[] result = new int[length];
    	
    	// Befülle das erzeugte Array mit der Hilfsmethode und gib es zurück:
        filterOdd(m, result, 0, 0);
        return result;
    }
    
    /**
     * Hilfsmethode, die das Ursprungsarray <m> mit einem dazugehörigen
     * Zähler <from> und das Ergebnisarray <result> mit einem zugehörigen
     * Zähler <to> erwartet. Die Methode betrachtet jeweils das Element
     * an der Position <from> und kopiert es in das Ergebnisarray (an
     * die Position <to>), falls es ungerade ist.
     */
    private static void filterOdd(int[] m, int[] result, int from, int to) {
    	// Rekursionsanker (alle Element aus m behandelt):
        if (from >= m.length)
            return;
        
        // Wenn Element an aktueller Position gerade ist, dann ohne Änderung
        // am Zielarray oder Zielposition mit nächstem Index rekursiv fortfahren.
        // Ansonsten vor dem Fortfahren Element kopieren und Zielzähler erhöhen:
        if (isEven(m[from])) {
            filterOdd(m, result, from+1, to);
        } else {
        	result[to] = m[from];
            filterOdd(m, result, from+1, to+1);
        }
    }
}