import java.util.*;
import java.lang.Math;

/**
 * 
 * @author MB
 * @version DEC 2017
 */
public class Rekursion
{
    /**
     * Die geraden Zahlen in einem Array werden rekursiv gezaehlt.
     * @param b - die Stelle, ab der gezaehlt wird, am Anfang mit dem Wert: 0
     */
    public static int geradeZahlenInEinemArray(int[] a, int ab){
        if(ab < 0 || ab > a.length){
            System.err.println("Ungültiger Parameter");
            return -1;
        }
        if(a.length == 0){
            return 0;   // leeres Array 
        }
        else if(ab == a.length - 1){   // Abbruchbedingung
            if(a[ab] % 2 == 0){
                return 1;
            }
            else{
                return 0;
            }
        }
        else{ 
            if(a[ab] % 2 == 0){
                return geradeZahlenInEinemArray(a,++ab) + 1;
            }
            else{
                return geradeZahlenInEinemArray(a,++ab);
            }
        }
    }

    /**
     * Methode zum rekursiven Ausgeben eines [String]-Arrays
     * @param ab - Stelle, ab der ausgegeben wird, beim ersten Aufruf: 0
     */
    public static void stringArrayAusgeben(String[] s, int ab){
        if(ab < 0 || ab > s.length){
            System.err.println("Ungültiger Parameter");
            return;
        }
        if(s.length == 0){
            return;   // leeres Array 
        }
        else if(ab == s.length - 1){   // Abbruchbedingung
            System.out.println(s[ab]);
        }
        else{ 
            System.out.println(s[ab]);
            stringArrayAusgeben(s,++ab);
        }
    }

    /**
     * Eine Methode, die rekursiv die positiven Vielfachen von 4 erkennt und nicht Division benutzt
     */
    public static boolean vielfachesVonVier(int n){
        if(n < 0){
            return false;
        }
        if(n == 0){
            return true;
        }
        if(vielfachesVonVier(n-4)){
            return true;
        }
        return false;
    }

    /**
     * Rekursive Definition der Fakultaet: n!
     * Basis: 0! = 1
     */
    public static int recursiveFactorial(int n){
        if (n == 0){
            return 1;}
        else if (n < 0){
            System.err.println("Invalid parameter");
            return -1;
        }
        else{
            return n * recursiveFactorial(n - 1);   // rekursiver Aufruf
        }
    }
    
    /**
     * Rekursive Definition der Multiplikation
     */
    public static long recursiveMultiplication(int a, int b){
        long result = 0;
        if ((a == 0) || (b == 0)){
            // do nothing
        }
        else if (b == 1){
            result = (long) a;
        }
        else {
            
                result = recursiveMultiplication(a,b-1) + a;
        }
        return result;
    }
     
     /** 
      * 
      * Rekursive Methode, um ein Zahlenarray aufzuaddieren, hier von hinten her (beim ersten Aufruf: n = a.length-1)
      * @param a - the integer array to be summed up
      * @param n - the position up to which one wants to sum up
      * @return - the sum of the integer array
      */
     
     public static long linearSumOfArray(int[] a,int n){
         if (n < 0){
             System.err.println("Illegaler Index");
             return -666;
         }
         else if (n == 0){
             return a[0];
         }
         else {
             return linearSumOfArray(a,n-1)+a[n]; // rekursiver Aufruf
         }
     }
     
     /** 
      * Rekursive Methode, um das Maximum eines Arrays zu bestimmen.
      * Es wird rekursiv jeweils ein Vergleich durchgefuehrt.
      * @param n - die Stelle bis zu der das Maximum bestimmt wird, also von hinten
      */
     public static int maximumOfArray(int[] a, int n){
         if (n < 0){
             System.err.println("Illegaler Index");
             return Integer.MIN_VALUE;
         }
         else if (n == 0){
             return a[0];
          }
         else {
              int max =  maximumOfArray(a,n-1);  // rekursiver Aufruf
              if (max >= a[n]){
                  return max;
              }
              else {
                  return a[n];
              }
          }
      }
     
    /**
     * Rekursive Summe eines zweidimensionalen Arrays
     * In einem zweidimensionalen Array bezieht sich der erste Index auf die Reihe, der zweite auf die Spalte:
     * a[2][3] - in der dritten Zeile das vierte Feld
     * @param A - das zu summierende Array
     * @param n - die Stelle ab der (von hinten her) das Array aufsummiert wird
     * @
     */ 
     
     public static long linearSumOfTwoDimensionalArray(int[][] a,int n){
         long result = 0;
         if (n < 0){
             System.err.println("Illegaler Index");
             return Long.MIN_VALUE;
         }
         else if (n == 0){
             result = a[0][0];
             return result;
         }
         else {
             for (int k = 0; k <= n; k++){ // adding the row with the index n up to [n][n]
                 result = result + a[n][k];
             }
             for (int k = 0; k < n; k++){  // [k < n] damit a[n][n] nicht zweimal addiert wird
                 result = result + a[k][n]; // adding the column with the index n
             }
             result = result + linearSumOfTwoDimensionalArray(a,n-1); // recursive call to previous square of side length n-1
             return result;
         }
     }
     
     /**
      * Rekursive Methode, um ein Array umzudrehen (zur Mitte hin)
      * @param A - the array to be reversed
      * @param i, j - the starting position of reversal
      * Aufruf: reverseArray(A,0,A.length-1)
      * This method is an example of tail recursion i.e. recursion is the last thing done by the method); 
      * tail recursion can be easily simulated by iteration     
      * 
      */
     public static void reverseArray(int[] A,int i, int j){
         int k;
         if (i < j){
             k = A[i];
             A[i] = A[j];
             A[j] = k;
             reverseArray(A,i+1,j-1);
         }
         return;
     }
     
     /**
      * Binaere Rekursion (i.e. using two recursive calls to halve the work)
      * @return the sum of the j integers starting at the index i
      */
     public static long binarySum(int[] a, int i, int j){
         if (i + j > a.length){
             System.err.println("So viele Zahlen sind nicht im Array!");
         }
         else if (j <= 1){
             return a[i];
         }
         return binarySum(a,i,(j/2)) + binarySum(a,i+(j/2),(j/2));
     }
     
    /**
     * computing Fibonacci numbers is linear, but exponential with binary recursion!
     * - because of overlapping recursive calls
     * @param k - integer the Fibonacci number of which is to be computed
     * @return result - an array of two long values holding a pair of Fibonacci numbers F(k) and F(k-1)
     */
     public static long[] linearFibonacci(int k){
       long[] result = new long[2];
       long l = 0;
       result[0] = 0;
       result[1] = 0;
       if (k <= 1){
           result[0] = k;
           return result;
       }
       else {
           result = linearFibonacci(k-1);
           l = result[0];
           result[0] = result[0] + result[1];
           result[1] = l;
           return result;
       }
    }

    /**
     * Rekursive Methode, um den Logarithmus zur Basis 2 zu bestimmen
     */
    public static long log2rec(long number){
        long result;
        result = (number / 2);
        if (result < 1){
            return 0;
        }
        else if (result < 2){
            return 1;
        }
        else {
            result = 1 + log2rec(result);
            return result;
        }
    }
    
    // Example: Drawing of a ruler
     /**
     * core method is drawRuler
     * @param nInches - how many inches the ruler takes
     * @param majorLength - the length of the major ticks on the ruler
     */
    protected static void drawOneTick(int tickLength){
        drawOneTick(tickLength,-1);     // rekursiver Aufruf
    }
    
    protected static void drawOneTick(int tickLength, int tickLabel){
        for(int i = 0; i < tickLength; i++){
            System.out.print("-");
        }
        if (tickLabel >= 0){
            System.out.print(" " + tickLabel);
        }
        System.out.print("\n");
    }
    
    protected static void drawTicks(int tickLength){
        if (tickLength > 0){
            drawTicks(tickLength - 1);  // rekursiver Aufruf
            drawOneTick(tickLength);
            drawTicks(tickLength - 1);
        }
    }
    
    public static void drawRuler(int nInches, int majorLength){
        drawOneTick(majorLength, 0);
        for(int i = 1; i <= nInches; i++){
            drawTicks(majorLength - 1);
            drawOneTick(majorLength, i);
        }
    }
     // End of ruler example //
}