Algorithm – Recursion
It may be useful to write a separate wrapper routine to do initialization for a complex recursive routine.Factorial routine that returns all of its intermediate results
int[] allFactorials(int n) { /* Wrapper routine */
int[] results = new int[n == 0 ? 1 : n];
doAllFactorials(n, results, 0);
return results;
}
int doAllFactorials(int n, int[] results, int level) {
if (n > 1) { /* Recursive case */
results[level] = n * doAllFactorials(n - 1, results, level + 1);
return results[level];
} else { /* Base case */
results[level] = 1;
return 1;
}
}
Permutations of a String
Implement a routine that prints all possible orderings of the characters in a string.
Treat each character in the input string as a distinct character, even if it is repeated.
To find all permutations starting at position n, successively place all allowable letters in position n, and for each new letter in position n find all permutations starting at position n + 1 (the recursive case). When n is greater than the number of characters in the input string, a permutation has been completed; print it and return to changing letters at positions less than n (the base case).
If you're past the last position
Print the string
Return
Otherwise
For each letter in the input string
If it's marked as used, skip to the next letter
Else place the letter in the current position
Mark the letter as used
Permute remaining letters starting at current position + 1
Mark the letter as unused
public static void permute(String str) {
int length = str.length();
boolean[] used = new boolean[length];
StringBuffer sb = new StringBuffer();
char[] in = str.toCharArray();
doPermute(in, sb, used, length, 0);
}
private static void doPermute(char[] in, StringBuffer sb, boolean[] used, int length,
int level) {
if (level == length) {
System.out.println(sb.toString());
return;
}
for (int i = 0; i < length; ++i) {
if (used[i])
continue;
sb.append(in[i]);
used[i] = true;
doPermute(in, sb, used, length, level + 1);
used[i] = false;
sb.setLength(sb.length() - 1);
}
}
Combinations of a String
These combinations range in length from one to the length of the string. Two combinations that differ only in ordering of their characters are the same combination.
For each letter from input start position to end of input string
Select the letter into the current position in output string
Print letters in output string
If the current letter isn't the last in the input string
Generate remaining combinations starting at next position with iteration starting
at next letter beyond the letter just selected
public static void combine( String str ){
int length = str.length();
char[] instr = str.toCharArray();
StringBuilder outstr = new StringBuilder();
doCombine( instr, outstr, length, 0, 0 );
}
private static void doCombine( char[] instr, StringBuilder outstr, int length,
int level, int start ){
for( int i = start; i < length; i++ ){
outstr.append( instr[i] );
System.out.println(outstr);
if( i < length - 1 ){
doCombine( instr, outstr, length, level + 1, i + 1 );
}
outstr.setLength(outstr.length() - 1);
}
}
Telephone Words
Write a routine that takes a seven-digit telephone number and prints out all of the possible "words" or combinations of letters that can represent the given number.
You can use the helper routine char getCharKey( int telephoneKey, int place )
If the current digit is past the last digit
Print the word because you're at the end
Else
For each of the three digits that can represent the current digit, going from
low to high
Have the letter represent the current digit
Move to next digit and recurse
If the current digit is a 0 or a 1, return
public static final int PHONE_NUMBER_LENGTH = 7;
public static void printTelephoneWords(int[] phoneNum) {
char[] result = new char[PHONE_NUMBER_LENGTH];
doPrintTelephoneWords(phoneNum, 0, result);
}
private static void doPrintTelephoneWords(int[] phoneNum, int curDigit, char[] result) {
if (curDigit == PHONE_NUMBER_LENGTH) {
System.out.println(String.valueOf(result));
return;
}
for (int i = 1; i <= 3; i++) {
result[curDigit] = getCharKey(phoneNum[curDigit], i);
doPrintTelephoneWords(phoneNum, curDigit + 1, result);
if (phoneNum[curDigit] == 0 || phoneNum[curDigit] == 1)
return;
}
}
Recursive Version:
Create the first word character by character
Loop infinitely:
Print out the word
Increment the last letter and carry the change
If the first letter has reset, you're done
private static final int PHONE_NUMBER_LENGTH = 7;
public static void printTelephoneWords(int phoneNum[]) {
char[] result = new char[PHONE_NUMBER_LENGTH];
int i;
/*
* Initialize the result (in our example, put GWP1WAR in result).
*/
for (i = 0; i < PHONE_NUMBER_LENGTH; i++)
result[i] = getCharKey(phoneNum[i], 1);
/* Main loop begins */
while (true) {
for (i = 0; i < PHONE_NUMBER_LENGTH; ++i) {
System.out.print(result[i]);
}
System.out.print('\n');
/*
* Start at the end and try to increment from right to left.
*/
for (i = PHONE_NUMBER_LENGTH - 1; i >= -1; i--) {
/*
* You're done because you tried to carry the leftmost digit.
*/
if (i == -1)
return;
/* Otherwise, we're not done and must continue. */
/*
* You want to start with this condition so that you can deal
* with the special cases, 0 and 1 right away.
*/
if (getCharKey(phoneNum[i], 3) == result[i] || phoneNum[i] == 0
|| phoneNum[i] == 1) {
result[i] = getCharKey(phoneNum[i], 1);
/* No break, so loop continues to next digit */
} else if (getCharKey(phoneNum[i], 1) == result[i]) {
result[i] = getCharKey(phoneNum[i], 2);
break;
} else if (getCharKey(phoneNum[i], 2) == result[i]) {
result[i] = getCharKey(phoneNum[i], 3);
break;
}
}
}
}
Print number in base m
public final class PrintInt {
private static final String DIGIT_TABLE = "0123456789abcdef";
private static final int MAX_BASE = DIGIT_TABLE.length();
// Print n in any base, recursively
// Precondition: n >= 0, 2 <= base <= MAX_BASE
private static void printIntRec(long n, int base) {
if (n >= base)
printIntRec(n / base, base);
System.out.print(DIGIT_TABLE.charAt((int) (n % base)));
}
// Driver routine
public static void printInt(long n, int base) {
if (base <= 1 || base > MAX_BASE)
System.err.println("Cannot print in base " + base);
else {
if (n < 0) {
n = -n;
System.out.print("-");
}
printIntRec(n, base);
}
}
}
public class BinarySearchRecursive
{
public static final int NOT_FOUND = -1;
public static <AnyType extends Comparable<? super AnyType>> int binarySearch( AnyType [ ] a, AnyType x )
{
return binarySearch( a, x, 0, a.length -1 );
}
// Hidden recursive routine.
private static <AnyType extends Comparable<? super AnyType>>
int binarySearch( AnyType [ ] a, AnyType x, int low, int high )
{
if( low > high )
return NOT_FOUND;
int mid = ( low + high ) / 2;
if( a[ mid ].compareTo( x ) < 0 )
return binarySearch( a, x, mid + 1, high );
else if( a[ mid ].compareTo( x ) > 0 )
return binarySearch( a, x, low, mid - 1 );
else
return mid;
}
}
public class BinarySearch
{
public static final int NOT_FOUND = -1;
public static <AnyType extends Comparable<? super AnyType>>
int binarySearch( AnyType [ ] a, AnyType x )
{
int low = 0;
int high = a.length - 1;
int mid;
while( low <= high )
{
mid = ( low + high ) / 2;
if( a[ mid ].compareTo( x ) < 0 )
low = mid + 1;
else if( a[ mid ].compareTo( x ) > 0 )
high = mid - 1;
else
return mid;
}
return NOT_FOUND; // NOT_FOUND = -1
}
}
Draw Ruler
public class Ruler extends Frame
{
private static final int theSize = 511;
public void paint( Graphics g )
{
drawRuler( g, 10, theSize - 1 + 10, 8 );
}
private void drawRuler( Graphics g, int left, int right, int level)
{
if( level < 1 )
return;
int mid = ( left + right ) / 2;
/*************
***** Uncomment this section to see the drawing in slow motion
try { Thread.sleep( 100 ); }
catch( InterruptedException e ) { }
*************/
g.drawLine( mid, 80, mid, 80 - level * 5 );
drawRuler( g, left, mid - 1, level- 1 );
drawRuler( g, mid + 1, right, level - 1 );
}
// Simple test program
// For simplicity, must terminate from console
public static void main( String [ ] args )
{
Frame f = new Ruler( );
f.setSize( theSize + 20, 110 );
f.setVisible( true );
}
}
Modulo operation
A ≡ B (mod n) if A and B have the same remainder when divided by n, we say that A is equivalent to B, modulo n.
Equivalently, A ≡ B (mod n) if and only if n is A divisor of B - A.
if A ≡ B (mod n), then:
1. A+C ≡ B+C (mod n)
2. AD ≡ BD (mod n)
3. for any positive number P, A^P ≡ B^P (mod n)
X= 3333^5555 (mod 10) = (3333 (mod 10))^5555 (mod 10) = 3^5555 (mod 10)
∵3^4 (mod 10) = 1
∴ X= 3^5555 (mod 10) = (3^4^1388 * 3^3 )(mod 10) = 3^3 (mod 10) = 7
Compute X^N (mod P)
/**
* Return x^n (mod p)
* Assumes x, n >= 0, p > 0, x < p, 0^0 = 1
* Overflow may occur if p > 31 bits.
*/
public static long power( long x, long n, long p )
{
if( n == 0 )
return 1;
long tmp = power( ( x * x ) % p, n / 2, p );
if( n % 2 != 0 )
tmp = ( tmp * x ) % p;
return tmp;
}
Greatest Common Divisor
public static long gcd(long m, long n) {
if (m < n) {
long t = m;
m = n;
n = t;
}
long r = m % n;
if (r == 0) {
return n;
} else {
return gcd(n, r);
}
}
LCD - Lowest common denominator
public static long lcd(long m, long n) {
return m*n/gcd(m,n);
}
Resources:
Data Structures and Problem Solving Using Java
Programming Interviews Exposed: Secrets to Landing Your Next Job, 2nd Edition
