// Arup Guha
// 4/1/2016
// Solution to Junior Knights OOP Recursion Homework

import java.util.*;

public class RecursionAssignment {

    public static void main(String[] args) {

        // Test each method.
        System.out.println("A geometric sum of 6 terms starting at 5 with a common ratio of 2 is "+geoSum(5, 6, 2));
        System.out.println("A arithmetic sum of 6 terms starting at 5 with a common difference of 2 is "+arithSum(5, 6, 2));
        System.out.println("The 10th Lucas number is "+lucas(10));
        System.out.println("The 10th TriFib number is "+trifib(10));
        System.out.println("13 choose 8 us "+binCoeff(13, 8));
        int[] array = {3, 7, 6, -2, 9, -17, 64, 2, -5};
        System.out.println("The sum of terms from index 2 to index 7 is "+sumArray(array, 2, 7));
        System.out.println("The 3n+1 sequence starting at 6 has "+threeNPlusOne(6)+" terms.");
    }

    // Returns the sum of the geometric sequence starting at first with common ratio ratio, with numterms terms.
    public static double geoSum(double first, int numterms, double ratio) {

        // If there are no terms, there is no sum =)
        if (numterms == 0) return 0;

        // Otherwise, add the first to the geometric series of n-1 terms starting at the 2nd term
        // of the original series.
        return first + geoSum(first*ratio, numterms-1, ratio);
    }

    // Returns the sum of the arithmetic sequence starting at first with common difference diff, with numterms terms.
    public static double arithSum(double first, int numterms, double diff) {

        // If there are no terms, there is no sum =)
        if (numterms == 0) return 0;

        // Otherwise, add the first to the arithmetic series of n-1 terms starting at the 2nd term
        // of the original series.
        return first + arithSum(first+diff, numterms-1, diff);
    }

    // Returns the nth Lucas number, for n >= 1.
    public static int lucas(int n) {

        // These are the two base cases.
        if (n == 1) return 1;
        if (n == 2) return 3;

        // The recursive definition is identical to Fibonacci.
        return lucas(n-1) + lucas(n-2);
    }

    // Returns the nth TriFib number.
    public static int trifib(int n) {

        // Easy way to write 3 base cases in one!
        if (n < 4) return n;

        // Similar to Fibonacci, with one term added!
        return trifib(n-1) + trifib(n-2) + trifib(n-3);
    }

    // Returns n choose k.
    public static int binCoeff(int n, int k) {

        // These two are always 1.
        if (k == 0 || k == n) return 1;

        // Definition given in the problem.
        return binCoeff(n-1, k-1) + binCoeff(n-1, k);
    }

    // Returns the sum of the values array[low...high].
    public static int sumArray(int[] array, int low, int high) {

        // No terms to sum...
        if (low > high) return 0;

        // Add the first term to the rest (calculated recursively).
        return array[low] + sumArray(array, low+1, high);
    }

    // Returns the length of the sequence generated starting at n, using the 3n+1 sequence rules.
    public static int threeNPlusOne(int n) {

        // Term ends here!
        if (n == 1) return 1;

        // For even terms, divide by two. We add 1 to count n.
        if (n%2 == 0) return 1 + threeNPlusOne(n/2);

        // Must be odd if we get here.
        return 1 + threeNPlusOne(3*n+1);
    }

}