CIS265 Chapter 20 – Lecture Notes – Code – Recursion
packagecsu.matos;
importjava.util.ArrayList;
importjava.util.Arrays;
publicclass Driver {
/**
* Author: Matos
* Date: 12-Sep-2011
* Goal: Introduce notion of recursion – Examine classic simple algorithms
*
*/
publicstaticvoid main(String[] args) {
int result0 = fact(6);
System.out.println("Factorial: " + result0);
int result1 = sum(6);
System.out.println("Summation " + result1);
int result2 = fib(6);
System.out.println("Fibonnacci " + result2);
printMsg("Hola", 6);
String s = "abba";
boolean result3 = isPalindrome(s);
System.out.println("Palindrome: " + s + " " + result3);
int[] list = { 55, 22, 44, 11, 88, 66, 77 };
showList(list);
//selectionSort(list, 0, list.length - 1);
selectionSort(list);
showList(list);
int key = 7;
int result4 = recursiveBinarySearch(list, key, 0, list.length - 1);
System.out.println("Bin. Search. key found at loc: " + result4);
// towers of Hanoi
moveDisks(3, 'A', 'B', 'C');
// Euclid's GCD
int result5 = gcd(300, 205);
System.out.println("GCD " + result5);
//eight queens
int[] queens = newint[8];
search(0, queens);
//traingular numbers
for (inti=1; i<7; i++) {
int result6 = triangular(i);
System.out.println(i + " Triangular " + result6);
}
//knapsack problem. Simple case - no optimization
ArrayList<Integer> items = newArrayList<Integer>(Arrays.asList(8, 2, 9, 4, 1, 5, 3, 4, 2, 6, 7));
ArrayList<Integer> solution = newArrayList<Integer>();
knapsack(16, solution, items);
for (int n : solution){
System.out.println("Knapsack: " + n );
}
}// main
privatestaticvoid knapsack(intmaxWeight, ArrayList<Integer> solution, ArrayList<Integer> items) {
if ((maxWeight >= 0 ) & (items.size()>0) ) {
int item = items.remove(0);
solution.add(0, item);
knapsack(maxWeight-item, solution, items);
}
else {
int item = solution.remove(0);
if (items.size()==0)
return;
else{
knapsack(maxWeight+item, solution, items);
}
}
}
// ////////////////////////////////////////////////
// triangular numbers
privatestaticint triangular(int n) {
if ( n == 1)
return 1;
else
return n + triangular(n-1);
}
// ////////////////////////////////////////////////
privatestaticint fact(int n) {
if ( n == 0 )
return 1;
else
return n*fact(n-1);
}
// start by calling: search(0);
// search for a solution starting on specified row
privatestaticboolean search(int row, int[] queens){
int SIZE = 8;
if (row == SIZE)
returntrue;
for (int column=0; column < SIZE; column++){
queens[row] = column; //place a queen at row,column
if (isValid(row, column, queens) & search(row+1, queens)){
System.out.println("Queen at: " + row + " : " + column);
returntrue;
}
}
returnfalse;
}//search
// check if a queen can be placed at row i and column j
privatestaticbooleanisValid(int row, int column, int[] queens){
for(inti=1; i<= row; i++){
if ( queens[row-i] == column //check diagonal
|| queens[row-i] == column - i //check upleft diagonal
|| queens[row-i] == column + i )//check upright diagonal
returnfalse;
}
returntrue;
}//isValid
// /////////////////////////////////////////////
privatestaticintgcd(int m, int n) {
if (m % n == 0)
return n;
else
returngcd(n, m % n);
}
// /////////////////////////////////////////////
privatestaticvoidmoveDisks(int n, charfromTower, chartoTower,
charauxTower) {
if (n == 1)
System.out.println("Move disk " + n + " from " + fromTower + " to "
+ toTower);
else {
moveDisks(n - 1, fromTower, auxTower, toTower);
System.out.println("Move disk " + n + " from " + fromTower + " to "
+ toTower);
moveDisks(n - 1, auxTower, toTower, fromTower);
}
}
// /////////////////////////////////////////////////////////////////////////////////
privatestaticintrecursiveBinarySearch(int[] list, int key, int low,
int high) {
if (low > high)
return -1 - low;
int mid = (low + high) / 2;
if (key < list[mid])
returnrecursiveBinarySearch(list, key, low, mid - 1);
elseif (key == list[mid])
return mid;
else
returnrecursiveBinarySearch(list, key, mid + 1, high);
}
// //////////////////////////////////////////////////////////////////////
privatestaticvoidselectionSort(int[] list) {
selectionSort(list, 0, list.length-1);
}
privatestaticvoidselectionSort(int[] list, int low, int high) {
if (low < high) {
intposMax = high;
inttheMax = list[high];
for (inti = 0; i < high; i++) {
if (list[i] > theMax) {
theMax = list[i];
posMax = i;
}// if
}// for
list[posMax] = list[high];
list[high] = theMax;
selectionSort(list, low, high - 1);
}// if
}
privatestaticvoidshowList(int[] list) {
System.out.println();
for (inti = 0; ilist.length; i++) {
System.out.print(list[i] + "\t");
}
}
// //////////////////////////////////////////////////////////////////////
privatestaticbooleanisPalindrome(String s) {
// deciding if s is a palindrome or not
returnisPalindrome(s, 0, s.length() - 1);
}
privatestaticbooleanisPalindrome(String s, int low, int high) {
if (low >= high)
returntrue;
elseif (s.charAt(low) != s.charAt(high))
returnfalse;
else
returnisPalindrome(s, low + 1, high - 1);
}
// /////////////////////////////////////////////////////////////////////////////
privatestaticvoidprintMsg(String msg, int times) {
// printing a message a number of times
if (times == 0)
return;
System.out.println(times + " " + msg);
printMsg(msg, times - 1);
}
// ///////////////////////////////////////////////////////////////////////////////
privatestaticint fib(int n) {
// finding the n-thfibonacci number
if ((n == 1) || (n == 0))
return 1;
else
returnfib(n - 2) + fib(n - 1);
}
// /////////////////////////////////////////////////////////////////////
privatestaticint sum(int n) {
// adding the first n integer numbers
if (n == 0)
return 0;
else
return (n + sum(n - 1));
}
}