/**
 * Recursion.java
 *
 * @author Jeff Ondich
 * 
 * Examples of simple recursion using integers, arrays, and strings.
 */

import java.util.*;

class Recursion
{
    public static void main( String[] args )
    {
        Scanner in = new Scanner( System.in );

        // Get an integer.
        System.out.print( "Number, please: " );
        int number = in.nextInt();

        // Compute its factorial.
        System.out.println( "-------------------" );
        int fact = recursiveFactorial( number );
        System.out.println( number + "! = " + fact  + " (recursive)" );
        fact = factorial( number );
        System.out.println( number + "! = " + fact + " (iterative)" );
        System.out.println( "" );
        System.out.println( "" );

        // Compute the Nth Fibonacci number.
        System.out.println( "-------------------" );
        System.out.println( "Twenty Fibonacci numbers:" );
        for( int k=1; k <= 20; k++ )
            System.out.print( fib( k ) + " " );
        System.out.println( "" );
        System.out.println( "" );

        // Create an array of random integers.
        System.out.println( "-------------------" );
        System.out.println( "Some random integers:" );
        int[] a = new int[10];
        for( int i=0; i < a.length; i++ )
            a[i] = (int)(Math.floor(Math.random() * 100) + 1);
        print( a, 0 );
        System.out.println( "" );

        // Compute its sum.
        number = sum( a, a.length );
        System.out.println( "Sum = " + number );
        System.out.println( "" );

        // Get a string, and determine whether it's a palindrome.
        System.out.println( "-------------------" );
        System.out.print( "String, please: " );
        String s = in.nextLine(); // clears out the previous line
        s = in.nextLine();
        if( isPalindrome( s ) )
            System.out.println( "\"" + s + "\" is a palindrome." );
        else
            System.out.println( "\"" + s + "\" is not a palindrome." );
    }


    // Problem: Medium n leads to very big time delay.
    public static int fib( int n )
    {
        if( n == 1  ||  n == 2 )
            return 1;

        return fib( n-1 ) + fib( n-2 );
    }


    public static int recursiveFactorial( int n )
    {
        System.out.println( "Starting recursiveFactorial " + n );
        if( n == 1 )
        {
            System.out.println( "Leaving recursiveFactorial " + n );
            return 1;
        }

        int total = n * recursiveFactorial( n - 1 );

        System.out.println( "Leaving recursiveFactorial " + n );

        return total;
    }


    public static int factorial( int n )
    {
        int result = 1;
        for( int i = 2; i <= n; i++ )
        {
            result = result * i;
        }

        return result;
    }


    public static int sum( int[] a, int length )
    {
        if( length <= 0 )
            return 0;

        int partialSum = sum( a, length - 1 );
        return a[length-1] + partialSum;
    }


    public static void print( int[] a, int startingAt )
    {
        if( startingAt >= 0  &&  startingAt < a.length )
        {
            System.out.print( a[startingAt] + " " );
            print( a, startingAt + 1 );
        }
    }


    public static boolean isPalindrome( String s )
    {
        if( s.length() <= 1 )
            return true;

        if( s.charAt(0) != s.charAt(s.length()-1) )
            return false;

        return isPalindrome( s.substring( 1, s.length() - 1 ) );
    }
}