Notes and Hacks from Recursion Student Teaching
Recursion Student Teaching
public class RecursionPattern {
public static void drawLine(int n) {
// Base case: when n becomes 0, stop the recursion
if (n == 0) {
return;
}
// Print n asterisks
for (int i = 1; i <= n; i++) {
System.out.print("*");
}
System.out.println();
// Recursively call drawLine with n-1
drawLine(n - 1);
}
public static void main(String[] args) {
int n = 10; // Number of lines
System.out.println("Pattern of asterisks:");
drawLine(n);
}
}
RecursionPattern.main(null);
/////////////////////////////// INSERTION SORT ///////////////////////////////
import java.util.ArrayList;
import java.util.Comparator;
class Country {
private String name;
private int size;
public Country(String name, int size) {
this.name = name;
this.size = size;
}
public String getName() {
return name;
}
public int getSize() {
return size;
}
}
class CountrySizeComparator implements Comparator<Country> {
@Override
public int compare(Country country1, Country country2) {
return Integer.compare(country2.getSize(), country1.getSize());
}
}
public class Main {
public static void main(String[] args) {
// Create ArrayList of Country objects
ArrayList<Country> countries = new ArrayList<>();
countries.add(new Country("Russia", 17125));
countries.add(new Country("Canada", 9985));
countries.add(new Country("USA", 9623));
countries.add(new Country("China", 9597));
countries.add(new Country("Brazil", 8516));
// Print unsorted list
System.out.println("Unsorted List:");
for (Country country : countries) {
System.out.println(country.getName() + " - " + country.getSize() + " sq km");
}
// Sort ArrayList using insertion sort and CountrySizeComparator
for (int i = 1; i < countries.size(); i++) {
Country key = countries.get(i);
int j = i - 1;
while (j >= 0 && countries.get(j).getSize() < key.getSize()) {
countries.set(j + 1, countries.get(j));
j--;
}
countries.set(j + 1, key);
}
// Print sorted list
System.out.println("\nSorted List (Decreasing Order by Size):");
for (Country country : countries) {
System.out.println(country.getName() + " - " + country.getSize() + " sq km");
}
}
}
Main.main(null);
/////////////////////////////// HEAP SORT ///////////////////////////////
import java.util.ArrayList;
import java.util.Comparator;
class Country {
private String name;
private int size;
public Country(String name, int size) {
this.name = name;
this.size = size;
}
public String getName() {
return name;
}
public int getSize() {
return size;
}
}
class CountrySizeComparator implements Comparator<Country> {
@Override
public int compare(Country country1, Country country2) {
// Compare by size in descending order
return Integer.compare(country2.getSize(), country1.getSize());
}
}
public class HeapSort {
public static void heapify(ArrayList<Country> arr, int n, int i, Comparator<Country> comparator) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && comparator.compare(arr.get(left), arr.get(largest)) > 0) {
largest = left;
}
if (right < n && comparator.compare(arr.get(right), arr.get(largest)) > 0) {
largest = right;
}
if (largest != i) {
Country swap = arr.get(i);
arr.set(i, arr.get(largest));
arr.set(largest, swap);
heapify(arr, n, largest, comparator);
}
}
public static void heapSort(ArrayList<Country> arr, Comparator<Country> comparator) {
int n = arr.size();
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i, comparator);
}
// One by one extract an element from heap
for (int i = n - 1; i > 0; i--) {
// Move current root to end
Country swap = arr.get(0);
arr.set(0, arr.get(i));
arr.set(i, swap);
// call max heapify on the reduced heap
heapify(arr, i, 0, comparator);
}
}
public static void main(String[] args) {
// Create an ArrayList of Country objects
ArrayList<Country> countries = new ArrayList<>();
countries.add(new Country("United States", 9834));
countries.add(new Country("Canada", 9984));
countries.add(new Country("Brazil", 8515));
countries.add(new Country("China", 9597));
countries.add(new Country("Russia", 17098));
countries.add(new Country("Australia", 7692));
System.out.println("Unsorted countries: ");
for (Country country : countries) {
System.out.println(country.getName() + " - Size: " + country.getSize());
}
// Sort countries in decreasing order using heap sort with custom comparator
heapSort(countries, new CountrySizeComparator());
System.out.println("\nCountries sorted by size in decreasing order: ");
for (Country country : countries) {
System.out.println(country.getName() + " - Size: " + country.getSize());
}
}
}
import java.util.ArrayList;
import java.util.Collections;
public class ArrayListOperations {
public static boolean areArrayListsEqualInReverse(ArrayList<Integer> list1, ArrayList<Integer> list2) {
// Check if the sizes of the two ArrayLists are equal
if (list1.size() != list2.size()) {
return false;
}
// Iterate through the ArrayLists in reverse order and compare the elements
for (int i = list1.size() - 1; i >= 0; i--) {
if (!list1.get(i).equals(list2.get(list1.size() - 1 - i))) {
return false;
}
}
// If all elements are equal in reverse order, return true
return true;
}
public static void overwriteArrayListWithAlphabet(ArrayList<String> list) {
// Create an ArrayList with the alphabet
ArrayList<String> alphabetList = new ArrayList<>();
for (char c = 'a'; c <= 'z'; c++) {
alphabetList.add(String.valueOf(c));
}
// Clear the original list and add all elements from the alphabetList
list.clear();
list.addAll(alphabetList);
}
public static void main(String[] args) {
ArrayList<Integer> list1 = new ArrayList<>();
ArrayList<Integer> list2 = new ArrayList<>();
// Add elements to list1 and list2
list1.add(1);
list1.add(2);
list1.add(3);
list2.add(3);
list2.add(2);
list2.add(1);
// Test if list1 and list2 contain the same elements in reverse order
boolean areEqualInReverse = areArrayListsEqualInReverse(list1, list2);
System.out.println("List 1: " + list1);
System.out.println("List 2: " + list2);
System.out.println("Are list1 and list2 equal in reverse order? " + areEqualInReverse);
ArrayList<String> list3 = new ArrayList<>();
// Add elements to list3
list3.add("apple");
list3.add("banana");
list3.add("cherry");
System.out.println("Original list3: " + list3);
overwriteArrayListWithAlphabet(list3);
System.out.println("After overwriting with alphabet: " + list3);
}
}
ArrayListOperations.main(null);