// file RecursiveIntFns.java
// Illustrations of simple recursive functions over the integers
//

// Since these are numerical functions, this is all non-object-oriented,
// C-style coding.
//
public  class RecursiveIntFns {

// Simple recursion
// Compute x^k for double x, integer k;

    public static double power(double x, int k)  {
        if (k==0) return 1.0;                
         else if (k>0) return x * power(x,k-1); 
         else return 1.0/power(x,-k);          
      }

    public static double fastPower(double x, int k)  {
        if (k==0) return 1.0;
        if (k==1) return x;
        if (k < 0) return 1.0/fastPower(x,-k);
        if (k%2 == 0) {     // k is even
           double p = fastPower(x,k/2);
           return p*p;
           }
        else {               // k is odd
           double p = fastPower(x,(k-1)/2);
           return x*p*p;
          }
        }

// Two recursive calls
// Compute the kth Fibonacci number in the really inefficient way

    public static int fib(int k) {
       if (k==0) return 1;              // Base case
       else if (k==1) return 1;         // Base case
       else return fib(k-2) + fib(k-1); // Recursive case
      }


// Mutually recursive functions
// Hailstone procedure, written with mutually recursively functions
// Returns the number of steps that the hailstone procedure takes to get to 1
// Look up the Wikipedia article on the "Collatz conjecture"

     public static int hailstone(int k) {
         System.out.print(k + "  ");
         if (k==1) return 0;
         else if (k % 2 == 0) 
                 return hsEven(k);
         else return hsOdd(k);
       }

     public static int hsEven(int k) {
           return 1+hailstone(k/2);
        }

     public static int hsOdd(int k) {
           return 1+hailstone(3*k+1);
        }

// Recursion with local variables. Factorial using addition. 
     public static int facAdd(int k) {
         int sum = 0;

         if (k <= 1) return 1;
         for (int i = 0; i < k; i++)
             sum = sum + facAdd(k-1);
         return sum;
      }


// Compute C(k,n), the number of combinations of size k out of n (Pascal's
// triangle) in the really inefficient way
//

    public static int combo(int k, int n) {
       int value;
       if (k < 0 || k > n) return -1;       // Error condition
       else if (k==0 || k==n) return 1;     // Base case
       else return
             combo(k,n-1) + combo(k-1,n-1); // Recursive case
     }

// Main procedure
//
    public static void main(String[] args) {
         System.out.println("power(3.0,4): " + power(3.0,4));
         System.out.println("power(2.0,-2): " +  power(2.0,-2));
         System.out.println("fastPower(3.0,9): " + fastPower(3.0,9));
         System.out.println("fib(4): " + fib(4));
         System.out.println("hailstone(7) Trace: " );
         System.out.println("Value: " + hailstone(7));
         System.out.println("facAdd(4): " + facAdd(4));
         System.out.println("combo(2,5): " + combo(2,5));
      }
}  // end RecursiveIntFns