### 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;

}

}

}

}

**P**

**rint 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