public class RekursiveFunktionen {

   static int fact(int n){
      if (n<= 1) return 1;
      else      return n*fact(n-1);
    }// end of fact

   static int ggT(int x, int y){
      if (x==y)     return x;
      else if (x>y) return ggT(x-y, y);
      else          return ggT(x, y-x);
    }// end of ggT 
    
   static void writeBin(int n){
      if (n<2) System.out.print(n);
      else{
          writeBin(n/2);
          System.out.print(n%2);
        }
    }// end of writeBin 

    // Seite 153
    static void hanoi(int n){ hanoi(n,'A','B','C'); }

    private static void hanoi(int n, char ausgang, char zwischen, char ziel){
      if(n==1) zieheScheibe(ausgang,ziel);
      else{
        hanoi(n-1,ausgang,ziel, zwischen);
        zieheScheibe(ausgang,ziel);
        hanoi(n-1,zwischen,ausgang,ziel);
        }
    }
    private static void zieheScheibe(char von, char nach){
      System.out.println("Scheibe von "+von+" nach "+nach);
    }
    
    // Seite 154
    static void nim(int n){
      int zug = 0;  
      if(n<3) zug=0;
      else if (!goodPos(n-7)) zug = 7;
      else if (!goodPos(n-5)) zug = 5;
      else zug = 3; // Möglicherweise Verlegenheitszug
      if(zug == 0) System.out.println("Ich gebe auf");
      else System.out.println("Ich nehme "+zug+" Steine"); 
    }
    
    private static boolean goodPos(int n){
      if(n<3) return false;
      else if (n <= 9) return true;
      else return !goodPos(n-7) 
               || !goodPos(n-5) 
               ||!goodPos(n-3); 
    }// end of goodPos
    
    // Seite 155
    static boolean even(int n){
        if (n==0) return true;
        else return odd(n-1);
    }    

    static boolean odd(int n){
        if (n==0) return false;
        else return even(n-1);
    }    
    
    // Seite 156
    static int UlamRek(int n){
       if (n==1) return 1;
       else if (even(n)) return UlamRek(n/2);
       else return UlamRek(3*n+1);
    }
    
    // Seite 157
    static int fibo(int n){
      if (n<2) return 1;
      else return fibo(n-2)+fibo(n-1);
    }
    
    static int mcCarthy(int n){
      if(n>100) return n-10;
      else return mcCarthy(mcCarthy(n+11));
    }
    
    static int fib(int n){ return fiboAux(n,1,1); }
    private static int fiboAux(int n, int acc1, int acc2){
      if (n==0) return acc1;
      else return fiboAux(n-1, acc2, acc1+acc2);
    }
}// Ende der Klasse RekursiveFunktionen