import java.util.Scanner;

/* Java class containing a collection of recursive methods, simply
** for the purpose of illustrating the concept of recursion.
** At least some of the methods are augmented so that they "narrate"
** their own execution by initially printing the argument(s) received
** and, just before exiting, the value returned (or otherwise the
** relevant result).
** Author: R. McCloskey
** March/April 2025
*/

public class RecursionExamples {

   // For the purpose of keeping track of the depth to which recursive
   // calls have descended, used for controlling how much each line
   // of "narration" is indented.
   private static int depth = -1;



   /* Returns the sum of the natural numbers up to and including n.
   ** The logic is based upon the observation that, for n>0, the sum of 
   ** the integers in the range [0..n] is the sum of the integers in the
   ** range [0..n-1], plus n.
   ** pre: n >= 0
   */
   public static int sumUpTo(int n) {
      // Start of entering narration
      depth = depth + 1;
      printSpaces(2*depth);
      System.out.println("Received " + n);
      // End of entering narration

      int result;
      if (n == 0) { result = 0; }  // base case
      else { result = sumUpTo(n-1) + n; }  // recursive case

      // Start of exiting narration
      printSpaces(2*depth);
      System.out.println("Received " + n + "; returning " + result);
      depth = depth - 1;
      // End of exiting narration

      return result;
   }
   
   /* Returns the largest value in a[low .. high).
   ** The logic is based upon the observation that, if a[low..high) is a
   ** segment of length at least two, then its largest value is the larger
   ** of a[low] and the largest value in a[low+1..high).
   ** pre: 0 <= low < high <= a.length
   */
   public static int maxOf(int[] a, int low, int high) {
      // Start of entering narration
      depth = depth + 1;
      printSpaces(2*depth);
      System.out.print("Received ");
      printArySeg(a, low, high);
      // End of entering narration

      int result;
      if (high-low == 1)   // base case (one-element segment)
         { result = a[low]; }
      else {  // recursive case
         int maxOfRest = maxOf(a, low+1, high);
         result = Math.max(a[low], maxOfRest);
      }

      // Start of exiting narration
      printSpaces(2*depth);
      System.out.print(result + " is max of " );
      printArySeg(a, low, high);
      depth = depth - 1;
      // End of exiting narration

      return result;
   }

   /* Returns the largest value in a[].
   ** The logic is based upon the observation that (the entirety of) a[]
   ** is just the array segment a[0..a.length).
   */
   public static int maxOf(int[] a) 
      { return maxOf(a, 0, a.length); }
   
   
   /* Reverses the elements in the segment a[low..high)
   ** The logic is based upon the observation that if a[low..high) is a
   ** segment of length two or more, reversing it is accomplished by
   ** swapping its first and last elements (i.e., the ones at locations
   ** low and high-1) and reversing the segment in between those two
   ** locations, namely a[low+1..high-1).
   */
   public static void reverseSegment(int[] a, int low, int high) {
      // Start of entering narration
      depth++;
      printSpaces(2*depth);
      System.out.print("Before reversing: ");
      printArySeg(a,low,high);
      // End of entering narration

      if (high - low < 2) { }  // base case (segment of length < 2)
      else {  
         swap(a, low, high-1);              // swap 1st and last elements
         reverseSegment(a, low+1, high-1);  // reverse segment in between
      }

      // Start of exiting narration
      printSpaces(2*depth);
      System.out.print("After reversing: ");
      printArySeg(a,low,high);
      depth--;
      // End of exiting narration
   }

   /* Reverses the elements in the given array.
   ** The logic is based on the observation that (the entirety of) a[] 
   ** is just a[0..a.length).
   */
   public static void reverse(int[] a) { reverseSegment(a, 0, a.length); }
   

   /* If x occurs in a[low..high), the value returned is the lowest-numbered
   ** location within a[low..high) containing x.  Otherwise, -1 is returned.
   ** The logic is based upon the observations that
   ** --no value, including x, occurs in an empty segment, 
   ** --if x == a[low], low is the lowest-numbered location in a[low..high)
   **   containing x,
   ** --if x != a[low], the lowest-numbered location containing x in
   **   a[low..high) is the lowest-numbered location in a[low+1..high)
   **   containing x
   */
   public static int indexOf(int[] a, int low, int high, int x) {
      // Start of entering narration
      depth++;
      printSpaces(2*depth);
      System.out.print("Finding " + x + " in ");
      printArySeg(a, low, high);
      // End of entering narration
      
      int result;
      if (low == high) { result = -1; }   // base case: empty segment
      else if (a[low] == x) { result = low; }
      else { result = indexOf(a, low+1, high, x); }

      // Start of exiting narration
      printSpaces(2*depth);
      System.out.print("Found " + x + " at location " + result + " in ");
      printArySeg(a, low, high);
      depth--;
      // End of exiting narration
      
      return result;
   }

   /* If x occurs in a[], the value returned is the lowest-numbered
   ** location within a[] containing x.  Otherwise, -1 is returned.
   ** The logic is based upon the observation that a[] is just
   ** a[0 .. a.length)
   */
   public static int indexOf(int[] a, int x) {
      return indexOf(a, 0, a.length, x);
   }

   /* Returns true iff x occurs somewhere in the segment a[low..high).
   ** The logic is based upon the observation that x occurs in a[low..high)
   ** iff the indexOf() method, when "asked" to find the lowest-numbered
   ** location in a[low..high) containing x, yields a value other than -1. 
   ** 0 <= low <= high <= a.length
   */
   public static boolean occursIn(int[] a, int low, int high, int x) {
      return indexOf(a, low, high, x) != -1;

      // Inferior approach that duplicates the logic in indexOf():
      //if (low == high) { return false; }
      //else {  // a[low..high) is not empty
      //   return a[low] == x  ||  occursIn(a, low+1, high, x);
      //}
   }
   
   /* Returns true iff x occurs somewhere within the given array.
   ** The logic is based upon the observation that (the entirety of)
   ** array a[] is just the segment a[0 .. a.length).
   */
   public static boolean occursIn(int[] a, int x) {
      return occursIn(a, 0, a.length, x);
   }
   
   
   /* Returns that k (low <= k <= high) such that every element in
   ** a[low..k) is less than x and every element in a[k..high) is 
   ** greater than or equal to x.
   ** The code is based upon the classic binary search algorithm.
   ** pre: 0 <= low <= high <= a.length and 
   **      all values in a[0..low) are < x and
   **      all values in a[high..a.length) are >= x and
   **      a[i] <= a[i+1] for all i satisfying 0 <= i < a.length-1
   */
   public static int indexOfAscending(int[] a, int low, int high, int x) {
      // Start of entering narration
      depth++;
      printSpaces(2*depth);
      System.out.print("Received x:" + x + " and ");
      printArySeg(a, low, high);
      // End of entering narration

      int result;
      if (low == high)     // base case (empty segment)
         { result = high; }
      else {
         int mid = (low + high) / 2;
         if (a[mid] < x) 
            { result = indexOfAscending(a, mid+1, high, x); }
         else   // a[mid] >= x
            { result = indexOfAscending(a, low, mid, x); }
      }

      // Start of exiting narration
      printSpaces(2*depth);
      System.out.print("Result:" + result + " having received x:" + x +
                         " and ");
      printArySeg(a, low, high); 
      depth--;
      // End of exiting narration

      return result;
   }

   /* Returns that k (low <= k <= high) such that every element in
   ** a[0..k) is less than x and every element in a[k..a.length) is 
   ** greater than or equal to x.
   ** pre: a[i] <= a[i+1] for all i satisfying 0 <= i < a.length-1
   */
   public static int indexOfAscending(int[] a, int x) {
      return indexOfAscending(a, 0, a.length, x);
   }
   
   /* Rearranges the elements in a[low..high) so that they are in ascending
   ** order (from least to greatest).  
   ** The logic is based upon the observation that to sort a[low..high)
   ** it suffices to swap the largest value in that segment with the
   ** value in location high-1 (thereby placing that largest value in
   ** its proper place within the segment) and then to sort a[low..high-1).
   */
   public static void selectSort(int[] a, int low, int high) {
      // Start of entering narration
      depth++;
      printSpaces(2*depth);
      System.out.print("Before sorting: ");
      printArySeg(a, low, high);
      // End of entering narration

      if (high - low < 2)   // segment of length < 2 
         { } 
      else {
         int locOfMax = locOfMax(a, low, high);
         swap(a, locOfMax, high-1);
         selectSort(a, low, high-1);
      }

      // Start of exiting narration
      printSpaces(2*depth);
      System.out.print("After sorting:  ");
      printArySeg(a, low, high);
      depth--;
      // End of exiting narration
   }

   /* Rearranges the elements in the given array to be in ascending order.
   ** The logic is based on the observation that (the entirety of) a[] is
   ** just a[0..a.length).
   */
   public static void selectSort(int[] a) 
      { selectSort(a, 0, a.length); }
   

   /* Returns a location within a[low..high) containing the maximum value
   ** in that segment.
   ** The logic is based upon the observation that, if a[low..high) is a
   ** segment of length at least two, then the largest value in that
   ** segment is either at location low or at a location containing the
   ** largest value in a[low+1..high), depending upon which of those two
   ** locations has the larger value.
   ** pre: 0 <= low < high <= a.length
   ** 
   */
   public static int locOfMax(int[] a, int low, int high) {
      // Start of entering narration
      depth++;
      printSpaces(2*depth);
      System.out.print("Finding max in: ");
      printArySeg(a, low, high);
      // End of entering narration

      int locOfMax;
      if (high - low == 1)   // one-element segment
         { locOfMax = low; }
      else {
         locOfMax = locOfMax(a, low+1, high);
         if (a[low] > a[locOfMax]) { locOfMax = low; }
      }

      // Start of exiting narration
      printSpaces(2*depth);
      System.out.print("Max at location " + locOfMax + " in: ");
      printArySeg(a, low, high);
      depth--;
      // End of exiting narration

      return locOfMax;
   }

   /* Returns a location within a[] containing its maximum value.
   ** The logic is based on the observation that a[] is just a[0..a.length).
   */
   public static int locOfMax(int[] a)
      { return locOfMax(a, 0, a.length); }


   // Private utility methods
   // -----------------------

   /* Swaps (i.e., interchanges) the values in the two specified
   ** locations of the specified array.
   ** pre: 0 <= j,k < a.length
   */
   private static void swap(int[] a, int j, int k) {
      int temp = a[j]; a[j] = a[k]; a[k] = temp;
   }
   

   /* Prints the values in the given array segment, each labeled by
   ** its location within the segment.  Skips to next line at the end.
   */
   private static void printArySeg(int[] a, int low, int high) {
      System.out.print('[');
      for (int i=low; i < high; i++) {
         System.out.printf("%d:%d ", i, a[i]);
      }
      System.out.println(']');
   }
   
   /* Prints the specified # of spaces.
   */
   private static void printSpaces(int k) {
      for (int i=0; i != k; i++)
         { System.out.print(' '); }
   }


   // main() method to illustrate the recursive methods above.

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

      // Compute a sum      
      System.out.println("\nCalling sumUpTo() to compute a sum:");
      System.out.println("-----------------------------------");
      sumUpTo(5);
      getResponse(keyboard);

      int[] ary = new int[] { 9, 7, 21, 5, 16, 3 };
      System.out.println("\nCalling maxOf() to compute a maximum:");
      System.out.println("-------------------------------------");
      maxOf(ary);
      getResponse(keyboard);

      System.out.println("\nCalling locOfMax() to compute the location of a maximum:");
      System.out.println("--------------------------------------------------------");
      locOfMax(ary); 
      getResponse(keyboard);
    
      System.out.println("\nCalling indexOf() to find a value that is present:");
      System.out.println("--------------------------------------------------");
      indexOf(ary, 5);
      getResponse(keyboard);

      System.out.println("\nCalling indexOf() to find a value not there:");
      System.out.println("--------------------------------------------");
      indexOf(ary, 4);
      getResponse(keyboard);

      System.out.println("\nCalling reverse() to reverse an array:");
      System.out.println("--------------------------------------");
      reverse(ary);
      getResponse(keyboard);

      System.out.println("\nCalling selectSort() to sort an array:");
      System.out.println("--------------------------------------");
      selectSort(ary);
      getResponse(keyboard);

      int[] b = new int[] { -2, 0, 4, 5, 8, 11, 11, 17, 21, 24, 25, 30, 35, 40, 42, 50};
                            
      System.out.println("\nCalling indexOfAscending() to do a search:");
      System.out.println("------------------------------------------");
      indexOfAscending(b, 5);
      getResponse(keyboard);

      System.out.println("\nCalling indexOfAscending() to do another search:");
      System.out.println("------------------------------------------------");
      indexOfAscending(b, 27);

      System.out.println("\nGoodbye.");
   }

   private static void getResponse(Scanner scanner) {
      System.out.print("\nHit ENTER to continue..");
      scanner.nextLine();
   }

}