Unit 4 Chapter 6 Recursion Code Flashcards
1
Q
triangle
A
import java.io.*;
////////////////////////////////////////////////////////////////
class TriangleApp
{
static int theNumber;
public static void main(String[] args) throws IOException
{
System.out.print("Enter a number: ");
theNumber = getInt();
int theAnswer = triangle(theNumber);
System.out.println("Triangle="+theAnswer);
} // end main()
//-------------------------------------------------------------
public static int triangle(int n)
{
if(n==1)
return 1;
else
return ( n + triangle(n-1) );
}
//-------------------------------------------------------------
public static String getString() throws IOException
{
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String s = br.readLine();
return s;
}
//-------------------------------------------------------------
public static int getInt() throws IOException
{
String s = getString();
return Integer.parseInt(s);
}
//--------------------------------------------------------------
} // end class TriangleApp
////////////////////////////////////////////////////////////////
2
Q
towers
A
////////////////////////////////////////////////////////////////
class TowersApp
{
static int nDisks = 3;
public static void main(String[] args)
{
doTowers(nDisks, 'A', 'B', 'C');
}
//-----------------------------------------------------------
public static void doTowers(int topN,
char src, char inter, char dest)
{
if(topN==1)
System.out.println("Disk 1 from " + src + " to "+ dest);
else
{
doTowers(topN-1, src, dest, inter); // src to inter
System.out.println("Disk " + topN + // move bottom
" from " + src + " to "+ dest);
doTowers(topN-1, inter, src, dest); // inter to dest
}
}
//-------------------------------------------------------------
} // end class TowersApp
////////////////////////////////////////////////////////////////
3
Q
stackTriangle2
A
import java.io.*; // for I/O
////////////////////////////////////////////////////////////////
class StackX
{
private int maxSize; // size of stack array
private int[] stackArray;
private int top; // top of stack
//--------------------------------------------------------------
public StackX(int s) // constructor
{
maxSize = s;
stackArray = new int[maxSize];
top = -1;
}
//--------------------------------------------------------------
public void push(int p) // put item on top of stack
{ stackArray[++top] = p; }
//--------------------------------------------------------------
public int pop() // take item from top of stack
{ return stackArray[top--]; }
//--------------------------------------------------------------
public int peek() // peek at top of stack
{ return stackArray[top]; }
//--------------------------------------------------------------
public boolean isEmpty() // true if stack is empty
{ return (top == -1); }
//--------------------------------------------------------------
} // end class StackX
////////////////////////////////////////////////////////////////
class StackTriangle2App
{
static int theNumber;
static int theAnswer;
static StackX theStack;
public static void main(String[] args) throws IOException
{
System.out.print("Enter a number: ");
System.out.flush();
theNumber = getInt();
stackTriangle();
System.out.println("Triangle="+theAnswer);
} // end main()
//-------------------------------------------------------------
public static void stackTriangle()
{
theStack = new StackX(10000); // make a stack
theAnswer = 0; // initialize answer
while(theNumber > 0) // until n is 1,
{
theStack.push(theNumber); // push value
--theNumber; // decrement value
}
while( !theStack.isEmpty() ) // until stack empty,
{
int newN = theStack.pop(); // pop value,
theAnswer += newN; // add to answer
}
}
//-------------------------------------------------------------
public static String getString() throws IOException
{
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String s = br.readLine();
return s;
}
//-------------------------------------------------------------
public static int getInt() throws IOException
{
String s = getString();
return Integer.parseInt(s);
}
//--------------------------------------------------------------
} // end class StackTriangle2App
////////////////////////////////////////////////////////////////
4
Q
stackTriangle
A
import java.io.*; // for I/O
////////////////////////////////////////////////////////////////
class Params // parameters to save on stack
{
public int n;
public int returnAddress;
public Params(int nn, int ra)
{
n=nn;
returnAddress=ra;
}
} // end class Params
////////////////////////////////////////////////////////////////
class StackX
{
private int maxSize; // size of StackX array
private Params[] stackArray;
private int top; // top of stack
//--------------------------------------------------------------
public StackX(int s) // constructor
{
maxSize = s; // set array size
stackArray = new Params[maxSize]; // create array
top = -1; // no items yet
}
//--------------------------------------------------------------
public void push(Params p) // put item on top of stack
{
stackArray[++top] = p; // increment top, insert item
}
//--------------------------------------------------------------
public Params pop() // take item from top of stack
{
return stackArray[top--]; // access item, decrement top
}
//--------------------------------------------------------------
public Params peek() // peek at top of stack
{
return stackArray[top];
}
//--------------------------------------------------------------
} // end class StackX
////////////////////////////////////////////////////////////////
class StackTriangleApp
{
static int theNumber;
static int theAnswer;
static StackX theStack;
static int codePart;
static Params theseParams;
//-------------------------------------------------------------
public static void main(String[] args) throws IOException
{
System.out.print("Enter a number: ");
theNumber = getInt();
recTriangle();
System.out.println("Triangle="+theAnswer);
} // end main()
//-------------------------------------------------------------
public static void recTriangle()
{
theStack = new StackX(10000);
codePart = 1;
while( step() == false) // call step() until it's true
; // null statement
}
//-------------------------------------------------------------
public static boolean step()
{
switch(codePart)
{
case 1: // initial call
theseParams = new Params(theNumber, 6);
theStack.push(theseParams);
codePart = 2;
break;
case 2: // method entry
theseParams = theStack.peek();
if(theseParams.n == 1) // test
{
theAnswer = 1;
codePart = 5; // exit
}
else
codePart = 3; // recursive call
break;
case 3: // method call
Params newParams = new Params(theseParams.n - 1, 4);
theStack.push(newParams);
codePart = 2; // go enter method
break;
case 4: // calculation
theseParams = theStack.peek();
theAnswer = theAnswer + theseParams.n;
codePart = 5;
break;
case 5: // method exit
theseParams = theStack.peek();
codePart = theseParams.returnAddress; // (4 or 6)
theStack.pop();
break;
case 6: // return point
return true;
} // end switch
return false;
} // end triangle
//-------------------------------------------------------------
public static String getString() throws IOException
{
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String s = br.readLine();
return s;
}
//-------------------------------------------------------------
public static int getInt() throws IOException
{
String s = getString();
return Integer.parseInt(s);
}
//--------------------------------------------------------------
} // end class StackTriangleApp
////////////////////////////////////////////////////////////////
5
Q
mergeSort
A
////////////////////////////////////////////////////////////////
class DArray
{
private long[] theArray; // ref to array theArray
private int nElems; // number of data items
//-----------------------------------------------------------
public DArray(int max) // constructor
{
theArray = new long[max]; // create array
nElems = 0;
}
//-----------------------------------------------------------
public void insert(long value) // put element into array
{
theArray[nElems] = value; // insert it
nElems++; // increment size
}
//-----------------------------------------------------------
public void display() // displays array contents
{
for(int j=0; j< theArray[highPtr] )
workSpace[j++] = theArray[lowPtr++];
else
workSpace[j++] = theArray[highPtr++];
while(lowPtr <n; j++)
theArray[lowerBound+j] = workSpace[j];
} // end merge()
//-----------------------------------------------------------
} // end class DArray
////////////////////////////////////////////////////////////////
class MergeSortApp
{
public static void main(String[] args)
{
int maxSize = 100; // array size
DArray arr; // reference to array
arr = new DArray(maxSize); // create the array
arr. insert(64); // insert items arr. insert(21); arr. insert(33); arr. insert(70); arr. insert(12); arr. insert(85); arr. insert(44); arr. insert(3); arr. insert(99); arr. insert(0); arr. insert(108); arr. insert(36); arr. display(); // display items arr. mergeSort(); // merge sort the array
arr.display(); // display items again
} // end main()
} // end class MergeSortApp
////////////////////////////////////////////////////////////////
6
Q
merge
A
////////////////////////////////////////////////////////////////
class MergeApp
{
public static void main(String[] args)
{
int[] arrayA = {23, 47, 81, 95};
int[] arrayB = {7, 14, 39, 55, 62, 74};
int[] arrayC = new int[10];
merge(arrayA, 4, arrayB, 6, arrayC);
display(arrayC, 10);
} // end main()
//-----------------------------------------------------------
// merge A and B into C
public static void merge( int[] arrayA, int sizeA,
int[] arrayB, int sizeB,
int[] arrayC )
{
int aDex=0, bDex=0, cDex=0;
while(aDex < sizeA && bDex < sizeB) // neither array empty
if( arrayA[aDex] < arrayB[bDex] )
arrayC[cDex++] = arrayA[aDex++];
else
arrayC[cDex++] = arrayB[bDex++];
while(aDex < sizeA) // arrayB is empty,
arrayC[cDex++] = arrayA[aDex++]; // but arrayA isn't
while(bDex < sizeB) // arrayA is empty,
arrayC[cDex++] = arrayB[bDex++]; // but arrayB isn't
} // end merge()
//-----------------------------------------------------------
// display array
public static void display(int[] theArray, int size)
{
for(int j=0; j);
}
//-----------------------------------------------------------
} // end class MergeApp
////////////////////////////////////////////////////////////////
7
Q
binary search
A
////////////////////////////////////////////////////////////////
class ordArray
{
private long[] a; // ref to array a
private int nElems; // number of data items
//-----------------------------------------------------------
public ordArray(int max) // constructor
{
a = new long[max]; // create array
nElems = 0;
}
//-----------------------------------------------------------
public int size()
{ return nElems; }
//-----------------------------------------------------------
public int find(long searchKey)
{
return recFind(searchKey, 0, nElems-1);
}
//-----------------------------------------------------------
private int recFind(long searchKey, int lowerBound,
int upperBound)
{
int curIn;
curIn = (lowerBound + upperBound ) / 2;
if(a[curIn]==searchKey)
return curIn; // found it
else if(lowerBound > upperBound)
return nElems; // can't find it
else // divide range
{
if(a[curIn] < searchKey) // it's in upper half
return recFind(searchKey, curIn+1, upperBound);
else // it's in lower half
return recFind(searchKey, lowerBound, curIn-1);
} // end else divide range
} // end recFind()
//-----------------------------------------------------------
public void insert(long value) // put element into array
{
int j;
for(j=0; j value) // (linear search)
break;
for(int k=nElems; k>j; k--) // move bigger ones up
a[k] = a[k-1];
a[j] = value; // insert it
nElems++; // increment size
} // end insert()
//-----------------------------------------------------------
public void display() // displays array contents
{
for(int j=0; j + searchKey);
} // end main()
} // end class BinarySearchApp
////////////////////////////////////////////////////////////////
8
Q
anagrm
A
///////////////////////////////////////////////////////////////
class AnagramApp
{
static int size;
static int count;
static char[] arrChar = new char[100];
//-----------------------------------------------------------
public static void main(String[] args) throws IOException
{
System.out.print("Enter a word: "); // get word
String input = getString();
size = input.length(); // find its size
count = 0;
for(int j=0; j< 99)
System.out.print(" ");
if(count < 9)
System.out.print(" ");
System.out.print(++count + " ");
for(int j=0; j);
}
//-----------------------------------------------------------
public static String getString() throws IOException
{
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String s = br.readLine();
return s;
}
//-----------------------------------------------------------
} // end class AnagramApp
////////////////////////////////////////////////////////////////
