/* ***************************************************************************
 $Workfile: Recursion.java$
   $Author: kalcock$
     $Date: 01/26/07 09:57:54$
 $Revision: 2$
 *****************************************************************************
 Package
 ****************************************************************************/
package com.keithalcock.t180;
/* ***************************************************************************
 Imports
 ****************************************************************************/

/* ***************************************************************************
 Class
 ****************************************************************************/
public class RecursionCode {

    /* ***********************************************************************
     1. This is the simplest recursive infinite loop I can imagine 
     ************************************************************************/
    public static void infiniteLoop() {
        infiniteLoop();
    }
    /* ***********************************************************************
     2. Methods don't need to call themselves directly.  Indirection is
     allowed.  Recursion may not be detected until runtime. 
     ************************************************************************/
    protected static void loop1(int a,int b,int c) {
        loop2(a,c);
    }
    
    protected static int loop2(int c,int b) {
        loop1(5,c+2,b+8);
        return 6;
    }
    
    public static void hiddenRecursion() {
        loop1(5,3,7);
    }
    /* ***********************************************************************
     3. There is no place for a counter, usually i, so it is passed as an
     argument instead.  It holds the "state" of our counting process.
     ************************************************************************/   
    public static void count(int n) {
        System.out.println(n);
        count(n+1);
    }
    /* ***********************************************************************
     4. In order to start the recursion without an argument, a helper function
     is sometimes used.      
     ************************************************************************/      
    public static void countFromZero() {
        count(0);
    }
    /* ***********************************************************************
     5. Since infinite loops aren't very useful, we keep track of where we are
     (cur, for current) and how far we need to go (max).      
     ************************************************************************/      
    public static void countFromUpTo(int cur,int max) {
        if (cur<=max) {
            System.out.println(cur);
            countFromUpTo(cur+1,max);
        }
    }
    /* ***********************************************************************
     6. It is very simple to change the order of output.  Simply switch
     the order of the lines.      
     ************************************************************************/         
    public static void backwardsCountFromUpTo(int cur,int max) {
        if (cur<=max) {
            backwardsCountFromUpTo(cur+1,max);
            System.out.println(cur);
        }
    }
    /* ***********************************************************************
     7. Recursion often uses -1 (it counts down), while iteration uses +1.
     We now have a typical condition for the base case.      
     ************************************************************************/             
    public static void backwardsCountFrom(int n) {
        if (n<0)
            return;
        System.out.println(n);
        backwardsCountFrom(n-1);
    }
    /* ***********************************************************************
     8. Even though we are now returning a result, no intermediate sum is
     required.  Subtotals are stored on the stack.  We now have a base case
     and a recursive case.  This is a prototype.      
     ************************************************************************/                
    public static int sumUpTo(int n) {
        if (n<0)
            return 0;
        return n+sumUpTo(n-1);
    }
    /* ***********************************************************************
     9. This might be straightforward now.
     ************************************************************************/                
    public static int factorial(int n) {
        if (n<1)
            return 1;
        return n*factorial(n-1);
    }
    /* ***********************************************************************
     10. A helper function and extra parameter are used here.  This divide and
     conquer strategy uses only one array element at a time.
     ************************************************************************/                
    protected static int arraySumFrom(int[] array,int n) {
        if (n<0)
            return 0;
        return array[n]+arraySumFrom(array,n-1);
    }
    
    public static int arraySum(int[] array) {
        return arraySumFrom(array,array.length-1);
    }   
    /* ***********************************************************************
     11. This might be straightforward now.
     ************************************************************************/                 
    protected static int arrayMinFrom(int[] array,int n) {
        if (n==0)
            return array[0];
        return Math.min(array[n],arrayMinFrom(array,n-1));
    }
    
    public static int arrayMin(int[] array) {
        return arrayMinFrom(array,array.length-1);
    }   
    /* ***********************************************************************
     12. A method can call itself twice.  The code matches the mathematical
     definition of Fibonacci.
     ************************************************************************/                     
    public static int fib(int n) {
        if (n<3)
            return 1;
        return fib(n-1)+fib(n-2);
    }
    /* ***********************************************************************
     13. Print the digits of a number one at a time.
     ************************************************************************/                         
    public static void print(int n) {
        int quotient=n/10;
        int remainder=n%10;
        
        if (quotient>0)
            print(quotient);
        System.out.print(remainder);
    }
    
    public static void println(int n) {
        print(n);
        System.out.println();
    }
    /* ***********************************************************************
     14. This is called Euclid's algorithm.  Find the greatest common factor
     of two numbers.
     ************************************************************************/                             
    public static int gcf(int left,int right) {
        int remainder=left%right;
        
        return remainder==0 ? right : gcf(right,remainder);
    }

    public static int lcm(int left,int right) {
        return left/gcf(left,right)*right;
    }
    /* ***********************************************************************
     15. More fun.  A palindrome is spelled the same forwards as backwards.
     ************************************************************************/
    public static boolean isPalindromeAt(String text,int left,int right) {
        if (left>=right)
            return true;
        if (text.charAt(left)!=text.charAt(right))
            return false;
        return isPalindromeAt(text,left+1,right-1);
    }    
    
    public static boolean isPalindrome(String text) {
        return isPalindromeAt(text,0,text.length()-1);
    }
    /* ***********************************************************************
     16. Most fun.  Solve x^2-6x-1=0.  Convert it to x^2=6x+1 or x=6+1/x.
     ************************************************************************/
    public static double continuousFraction(int n) {
        double value;

        if (n<0)
            return 1.0;
        value=1.0+6.0/continuousFraction(n-1);
        System.out.println(n+" "+value);
        return value;
    }    
    /* ***********************************************************************
     17. Try it all out.
     ************************************************************************/                                
    public static void main(String[] args) {
//        infiniteLoop();
//        hiddenRecursion();
//        count(0);
//        countFromZero();
//        countFromUpTo(0,10);
//        backwardsCountFromUpTo(0,10);
//        backwardsCountFrom(10);
//        System.out.println(sumUpTo(5));       
//        System.out.println(factorial(5));       
//        System.out.println(arraySum(new int[]{1,2,3,4,5}));
//        System.out.println(arrayMin(new int[]{3,4,5,1,2}));
//        System.out.println(fib(6));
//        println(12345);
//        System.out.println(gcf(6,22));
//        System.out.println(lcm(6,21));
//        System.out.println(isPalindrome("bob"));
//        System.out.println(isPalindrome("the"));
        System.out.println(continuousFraction(40));
    }
}
/* **************************************************************************/