AP Computer Science Study Guide as Computer Program Take 2

<![CDATA[/*>

AP Computer Science Study Guide Take 2

Introduction

This guide was started in a previous article with comments for language elements an AP Student should know and be able to give a code example. This incantation of the same topic fills in most of the blanks with coding examples. If you were a good student you should be able to compare yours to mine. If you are a lazy student (meaning you didn't try to add any of your own code to the study guide) you better look through the code examples carefully and make sure they look familiar to you.
How to use this guide:

• Pull the code into your IDE in its own project and run the program.
• Generate the javadoc for the project. There should be a menu command to do it. In netbeans in was found in the run menu. For eclipse users if you can't find a quick web search should give you an answer.
• Read through the code. The comments tell the story of what is going on.
• Print out
  • the JavaDoc
  • the code
  • the output
• Place them side by side on a large table and look through line by line and find where things are happening and why.

Things to look for

Different Types of Java Comments

The AP overview indicates you should be aware of the various types of comments. The most complex is the Javadoc style block comment. It contains @param and @return metafunctions in them. These comments start with /** and have *'s beginning each line with a terminating */ (on the last line). If they occur just before a method or class declaration the text within the comment will appear in the generated Javadoc. There are 2 other forms of comments one the // is used extensively in the APSubset code. The regular block comment /* . . . */ is shown only once.
The reason to point this out to you is that large portions of the code have to be used to engage the Java comments in an insignificant way. Where most of the java code examples can be accomplished with a few lines of code and a few output statements.

Method overloading

This functionality is spread in 2 different sections of code. The reverse method is defined twice. Once for Strings and then for integers. It is then used in the main method showing how the call signatures are the same and only the parameters change.

Exceptions

This could almost be done within the main method alone except that you also need to know about throwing an Exception. For this I created a small method that looks at its 'int' input parameter and throws an Exception if the parameter is the 'int' 3. Otherwise it just prints some diagnostic text to let you know it was called. The AP document was not too specific about which 'Exception's you should know about. I picked 3 that I thought you may have come across already in your projects. The fourth 'Exception' used is the parent class for Exceptions. Using this class is a useful way to catch Exceptions when your not sure which ones are likely to be thrown.
The reason for try-catch-finally and 'Exceptions' are to allow a program to either die gracefully or recover from an error. They are used extensively in large programming projects and Java does a nice job of integrating them in a modular way.
The 'finally' clause is run after every exception 'catch' clause has completed. In the code set up in APSubset the try catch block is run in a loop. The loop is set up to simulate a different error during each iteration. In a more robust program the try-catch block may be around your entire code. Remember most of the time Exceptions are things to avoid in the design of your code. You put them in because you may not be aware of every error scenario that could occur. In a small example such as this I had to force things to happen in a very small space. The idea behind 'finally' is that it gives you a guarenteed exit point from any Exception. A place where you can reset things or decide that the error involved was too grave and you must terminate the program. It's a place where common error handling or recovery can be done.
In the exception code there is a line commented out. It does a divide by zero but it is outside the try-catch block. Uncomment it in the IDE and run the code. You should find that the program will terminate there and no other statements past that point will be executed. Now compare that with the way the zero divide works inside the try-catch block. That should give you an idea of the utility of the Exception handling facilities in Java.

APSubset.java

The code is 600+ lines of code so rather than place it in the text of the article I have made it into a downloadable file. Go ahead and download it and run it yourself in your own Java IDE.
APSubset.java

Output (Run from Netbeans IDE)

run:
APSubset: BASIC TYPES
APSubset: int a = 0
APSubset: double b = 0.0
APSubset: boolean c = false
APSubset: 

APSubset: BASIC OPERATORS
APSubset: int a = 1 + 2 = 3
APSubset: double b = 2.0 + 3.5 = 5.5
APSubset: int a = 2 - 3 = -1
APSubset: double b = 2.0 - 3.5 = -1.5
APSubset: int a = 2 * 3 = 6
APSubset: double b = 2.0 * 3.5 = 7.0
APSubset: int a = 3 / 2 = 1
APSubset: double b = 3.5 / 2.0 = 1.75
APSubset: int a = 17 % 5 = 2
APSubset: double b = 17.0 % 6.0 = 5.0
APSubset: 

APSubset: Pre/Post-increment and Pre/Post-decrement
APSubset: int a = 2
APSubset: a++ = 2
APSubset: int a = 3
APSubset: ++a = 4
APSubset: int a = 4
APSubset: a-- = 4
APSubset: int a = 3
APSubset: --a = 2
APSubset: int a = 2
APSubset: double b = 5.0
APSubset: b++ = 5.0
APSubset: double b = 6.0
APSubset: ++b = 7.0
APSubset: double b = 7.0
APSubset: b-- = 7.0
APSubset: double b = 6.0
APSubset: --b = 5.0
APSubset: double b = 5.0
APSubset: 

APSubset: Assignment operators +=, -=, *=, /=, %=
APSubset: int a = 13
APSubset: double b = 13.0
APSubset: int a += 7 = 20
APSubset: double b += 7.5 = 20.5
APSubset: int a -= 3 = 17
APSubset: double b -= 3.5 = 17.0
APSubset: int a *= 2 = 34
APSubset: double b *= 2.0 = 34.0
APSubset: int a /= 2 = 17
APSubset: double b /= 2.0 = 17.0
APSubset: int a %= 5 = 2
APSubset: double b %= 6.0 = 5.0
APSubset: boolean c = 1 == 1 = true
APSubset: boolean c = 2 != 3 = true
APSubset: boolean c = 2 < 1 = false
APSubset: boolean c = 2 < 3 = true
APSubset: boolean c = 2 <= 4 = true
APSubset: boolean c = 2 <= 2 = true
APSubset: boolean c = 4 > 1 = true
APSubset: boolean c = 4 >= 5 = false
APSubset: boolean c = 5 >= 5 = true
APSubset: 

APSubset: Logical Operators ||, &&, !
APSubset: boolean c = true || true = true
APSubset: boolean c = true || false = true
APSubset: boolean c = false || false = false
APSubset: boolean c = true && true = true
APSubset: boolean c = true && false = false
APSubset: boolean c = false && false = false
APSubset: int[] d = null: in else clause due to short circuit
APSubset: int[] d = 1  2  3  4  5  
APSubset: double b = 5.0/2 = 2.5
APSubset: double b = (int) b = 2.0
APSubset: int a = (int) 5.0/2 = 2
APSubset: double b = 5.0/(int) 2 = 2.5
APSubset: double b = (int) 5.0/(int) 2 = 2.0
APSubset: double b = ((int) 5.0)/(double) 2 = 2.5
APSubset: double b = ((int) 5.0)/ 2 = 2.0
APSubset: Take a string, concat a number13and another string
APSubset: to see a back slash must escape it with a backslash \\ = \
APSubset: to print a double quote use backslash double quote \" = "
APSubset: 
 to get
 extra 
 lines use backslash-n (\n) 

APSubset: Look at the code for this because there are some interesting \ (backslash) uses


APSubset: One Dimension Array: Size = 5  array = 0 1 2 3 4
APSubset: Notice in the code that the size is 5 and the indexes range from 0 - 4
APSubset: Output 2 x 2 array in matrix form
0  1   
1  0   
APSubset: twod[0].size = 2
APSubset: twod[1].size = 2
APSubset: twod.size = 2
APSubset: if statements: single statement follows
APSubset:   stmt1:
APSubset:   single statement if: 1 < 2
APSubset:   stmt2:
APSubset: if statements: compound statements
APSubset:   stmt1:
APSubset:   compound if:
APSubset:   1 < 2 is true
APSubset:   all statements are executed within braces
APSubset:   stmt2:
APSubset: only 1 of the if statement is executed in the compound ifs
APSubset: then clause: num + 5 < 20 is true
APSubset: else clause: num + 15 < 20 is false
APSubset: while loop: count numbers from 0 to 9
0 1 2 3 4 5 6 7 8 9 APSubset: end while loop
APSubset: for loop: version of above while loop
APSubset: for(i = 0; i < 10; i++): all loop controls are in first line (you don't have to search through the loop)
0 1 2 3 4 5 6 7 8 9 APSubset: end for loop
APSubset: for each: use on intarr defined above, check the difference
APSubset: this version uses the fact that if you are going to visit each element
APSubset: the computer knows the size and can automatically code the loop parameters
0 1 2 3 4 APSubset: end for each style loop
APSubset: new operator: using new to create an object instance of APSubset
APSubset: this will give us an object to use the 'reverse' methods defined above
APSubset: apsubset instantiated to an APSubset object
APSubset: method over loading: 2 reverses have been defined:
APSubset: one to reverse strings and one to give a string of reversed 'int'
APSubset: look at their definitions they have different call parameters
APSubset: the compiler figures out which one to use based on parameter type
APSubset: apsubset.reverse("abcdefg") = gfedcba
APSubset: apsubset.reverse(12345) = 54321
APSubset: The methods do similar things but to different types of parameters.
APSubset: Run your IDE JavaDoc on this class and you will see what different
APSubset: comment styles do for the JavaDoc Documentation.
APSubset: Single line comments starting with // are used copiously in this class
APSubset: these 'log' statements are defined as static they can be used anywhere
APSubset: inside this class definition. If one were to use it in another class
APSubset: would have to use: APSubset.log();
APSubset: APSubset.log() call check the code
APSubset: static field: APSubset.ANSWER = 42
APSubset: String nullstr = null;  can't print this because it's null it has no String value yet
APSubset: We can test if the variable is a null variable
APSubset: null: reserved variable name value is null
APSubset: if (e = true): Forgot the extra equal sign setting e to true rather than testing with ==
APSubset: e = true; f = false
APSubset: if (e = f): in else clause because of '=' assignment now e is false
APSubset: e = true; f = true
APSubset: if (e == f): Now this works as expected.
APSubset: Be careful with your use of = and == especially with booleans
APSubset: exceptionGeneratorMethod executed no exception thrown ctr = 0
APSubset: try-catch ArithmeticException: / by zero
APSubset: finally clause executed: j = 0
APSubset: exceptionGeneratorMethod executed no exception thrown ctr = 1
APSubset: try-catch NullPointerException: null
APSubset: finally clause executed: j = 1
APSubset: exceptionGeneratorMethod executed no exception thrown ctr = 2
APSubset: loop past intarr boundry
0 1 2 3 4 APSubset: try-catch IndexOutOfBoundsException: 5
APSubset: finally clause executed: j = 2
APSubset: try-catch Exception: exeptionGenerator Method: ctr = 3
APSubset: finally clause executed: j = 3
APSubset: java.lang.Object
APSubset:  
APSubset: java.lang.Integer
APSubset: Integer myint = new Integer(55) therefore myint.intValue() = 55
APSubset: Integer.MIN_VALUE = -2147483648
APSubset: Integer.MAX_VALUE - 2147483647
APSubset:  
APSubset: java.lang.Double
APSubset: Double mydub = new Double(35.75) therefore mydub.doubleValue() = 35.75
APSubset:  
APSubset: java.lang.String
APSubset: String test_str = "this has 22 characters"
APSubset: test_str.length = 22
APSubset: test_str.substring(4,10) =  has 2
APSubset: test_str.substring(4) -  has 22 characters
APSubset: test_str.indexOf("has") = 5
APSubset: test_str.compareTo("this has 22 characters") = 0
APSubset: test_str.compareTo("this has 22 characters") = 19
APSubset: test_str.compareTo("this has 22 characters") = -6
APSubset:  
APSubset: java.lang.Math
APSubset: Math.abs(-3) = 3
APSubset: Math.abs(-3.56) = 3.56
APSubset: Math.pow(2.0,5.0) = 32.0
APSubset: Math.sqrt(2.0) = 1.4142135623730951
APSubset: Math.random() = 0.025126650838768416
APSubset: Math.random() = 0.8468764801673784
APSubset: Math.random() = 0.5932715934489992
APSubset:  
APSubset: Added values to end of list in succession: 
1 2 3  
APSubset: intList.size() = 3
APSubset: Added 4 to end of list: inList.size() = 4
APSubset: intList.get(2) = 3
APSubset: intList.add(2,5): 
1 2 5 3 4  
APSubset: Added 5 to each value using intList set: 
6 7 10 8 9  
APSubset: intList.remove(1): 
6 10 8 9  
APSubset: intList.remove(2): 
6 10 9  
APSubset: Because remove shifts the elements the 2 method calls end up removing
APSubset: elements at index 1 and 3 of the original array
BUILD SUCCESSFUL (total time: 1 second)

APSubset JavaDoc

A pdf of the JavaDoc Generated from netbeans can be downloaded from:
APSubset JavaDoc

Conclusion

There are still some things from the AP document not coded. Some of them were outside the scope of this type of study guide. Some I couldn't think of a simple yet elegant example. I've marked those in the comments of the APSubset code. Most of them you should have been exposed to in projects you've done in your class.
This study guide is meant to remind you of the functional elements of Java available to you during your AP Test. I think it is more of a guide for the free response problems. Helping you to cast your answers in the subset so that you don't over think the problem or over utilize functionality available in advanced libraries.
I did not cover the Grid World case study in this and certainly that is something you need to look over and understand. The idea here was to cover the foundational elements of Java by way of a program so you may remember them if you need them.

References

1. https://apstudent.collegeboard.org/apcourse/ap-computer-science-a/course-details "Course Details." AP Computer Science A. N.p., n.d. Web. 29 Mar. 2013.

Author: Nasty Old Dog

-->

Merge Sort

Introduction

Merge sort works based on the fact that it is relatively easy to take 2 sorted lists and merge them into a larger sorted list. Once we have a merge operation the rest of the sorting routine is relatively simple. Merge sort is also a faster sorting algorithm than either selection sort or insertion sort (on moderate sized lists or arrays anyway). It has to do with the divide and conquer structure of the recursive solution. Merge sort's one draw back is that it is memory intensive. At each level of recursion a new list has to be created to hold the merged smaller lists until the program get's back to the top level call where a new list of sorted elements is provided. In the other 2 sorts the sorting is done inline and only a 'tmp' variable is needed to swap the values when necessary. Memory used to be a big thing now adays not so much. Memory for computers is relatively cheap and many gigabytes may be had for a few hundred dollars.

Merge operation

I will develop the merge sort in the same SortLab class as the other sort routines. First step in the merge sort is let's develop the merge operation.

Specifications

• Take two int[] parameters that are assumed to be sorted
• return a new int[] whose length is the size of list1.length + list2.length
• The returned int[] should have its elements sorted in ascending order

Even though the lists are sorted this operation needs to track a few things:

• One array may run out of elements early at which point just add in the last elements from the other array
• Even if they alternate they may not alternate evenly so we must track where we are in each contributing array
• In the first round of testing merge will be a static routine. Once we go to a full merge sort we will instantiate an object as we did for the other routines

merge code

public static int[] merge(int[] a, int[] b)
{
    int[] m = new int[a.length + b.length];
    int i=0;
    int j=0;

    for (int k = 0; k < m.length; k++)
    {
        if (i < a.length && j < b.length) {
        if (a[i]<=b[j]) {
            m[k] = a[i];
            i++;
        }
        else {
            m[k] = b[j];
            j++;
        }
        }
        else if (i < a.length) {  // b exhausted use up a
            m[k] = a[i];
            i++;
        }
        else { // b still has some left use up those
            m[k] = b[j];
            j++;
        }
    }
    return m;
}

public static void main(String[] args) {
    SortLab select = new SortLab();
    SortLab selectA = new SortLab();
    SortLab insert = new SortLab();
    SortLab insertA = new SortLab();

    System.out.println("Selection Sort");
    System.out.print("unsorted: ");
    select.display();
    select.selection();
    System.out.print("sorted:   ");
    select.display();
    System.out.println("SelectionA Sort");
    System.out.print("unsorted: ");
    selectA.display();
    selectA.selectionA();
    System.out.print("sorted:   ");
    selectA.display();
    System.out.println();
    System.out.println();
    System.out.println("Insertion Sort");
    System.out.print("unsorted: ");
    insert.display();
    insert.insertion();
    System.out.print("sorted:   ");
    insert.display();
    System.out.println("Insertion Sort with Explicit Shift");
    System.out.print("unsorted: ");
    insertA.display();
    insertA.insertion();
    System.out.print("sorted:   ");
    insertA.display();

    System.out.println("Merge Testing");
    int[] l1 = {0, 2, 3, 4, 6, 7, 9};
    int[] l2 = {1, 3, 5, 8, 10};
    int[] l3 = merge(l1,l2);
    for (int i : l3)
    {
        System.out.print(i + " ");
    }
    System.out.println();
}    

Output 1

run:
Selection Sort
unsorted: 9  6  2  1  3  7  8  4  0  5  
interim:  0  6  2  1  3  7  8  4  9  5  
interim:  0  1  2  6  3  7  8  4  9  5  
interim:  0  1  2  6  3  7  8  4  9  5  
interim:  0  1  2  3  6  7  8  4  9  5  
interim:  0  1  2  3  4  7  8  6  9  5  
interim:  0  1  2  3  4  5  8  6  9  7  
interim:  0  1  2  3  4  5  6  8  9  7  
interim:  0  1  2  3  4  5  6  7  9  8  
interim:  0  1  2  3  4  5  6  7  8  9  
sorted:   0  1  2  3  4  5  6  7  8  9  
SelectionA Sort
unsorted: 9  0  5  7  2  8  4  3  1  6  
interim:  0  9  5  7  2  8  4  3  1  6  
interim:  0  1  5  7  2  8  4  3  9  6  
interim:  0  1  2  7  5  8  4  3  9  6  
interim:  0  1  2  3  5  8  4  7  9  6  
interim:  0  1  2  3  4  8  5  7  9  6  
interim:  0  1  2  3  4  5  8  7  9  6  
interim:  0  1  2  3  4  5  6  7  9  8  
interim:  0  1  2  3  4  5  6  7  9  8  
interim:  0  1  2  3  4  5  6  7  8  9  
sorted:   0  1  2  3  4  5  6  7  8  9  


Insertion Sort
unsorted: 3  0  5  2  6  4  7  9  1  8  
interim:  0  3  5  2  6  4  7  9  1  8  
interim:  0  3  5  2  6  4  7  9  1  8  
interim:  0  2  3  5  6  4  7  9  1  8  
interim:  0  2  3  5  6  4  7  9  1  8  
interim:  0  2  3  4  5  6  7  9  1  8  
interim:  0  2  3  4  5  6  7  9  1  8  
interim:  0  2  3  4  5  6  7  9  1  8  
interim:  0  1  2  3  4  5  6  7  9  8  
interim:  0  1  2  3  4  5  6  7  8  9  
sorted:   0  1  2  3  4  5  6  7  8  9  
Insertion Sort with Explicit Shift
unsorted: 1  9  3  8  5  7  6  4  0  2  
interim:  1  9  3  8  5  7  6  4  0  2  
interim:  1  3  9  8  5  7  6  4  0  2  
interim:  1  3  8  9  5  7  6  4  0  2  
interim:  1  3  5  8  9  7  6  4  0  2  
interim:  1  3  5  7  8  9  6  4  0  2  
interim:  1  3  5  6  7  8  9  4  0  2  
interim:  1  3  4  5  6  7  8  9  0  2  
interim:  0  1  3  4  5  6  7  8  9  2  
interim:  0  1  2  3  4  5  6  7  8  9  
sorted:   0  1  2  3  4  5  6  7  8  9  
Merge Testing
0 1 2 3 3 4 5 6 7 8 9 10 

Splitting the list

Splitting is the next thing to tackle, the straight forward way would be to just add the beginning index and the ending index together and divide by 2. This cuts the list in half. If we start with a list with 10 things in it, the starting index = 0 and the ending index = 9. (0+9)/2 = 4 we split the list after four (4). This gives us 2 lists from 0 - 4 and 5 - 9. We then want to split the list again and again until ideally all we are left with is 10 single element list. If you work this out on various size arrays you end up needing to help a little when you get to a pair of indexes. So my implementation will treat single indexes and pair indexes as the test case for recursion.

Given the above for background lets look at some pseudo code. I will assume that the original list is the labArray field and mergesort will track indexes into that array.

public int[] mergesort(int begin, int end)
{
  int[] newArray = null;
  if (begin == end) { 
    // This is the end of the road create a new list of 1 element
    newArray = new int[1];
    newArray[0] = this.labArray[begin];
    return newArray;
  }
  if (1 == end-begin) {
    // down to 2 elements 
    newArray = new int[2];
    if ( this.labArray[begin] < this.labArray[end]) {
      newArray[0] = this.labArray[begin];
      newArray[1] = this.labArray[end];
    } else {
      newArray[0] = this.labArray[end];
      newArray[1] = this.labArray[begin];
    }
    return newArray;
  }
  int split = (begin + end)/2;
  return merge(mergesort(begin, split), mergesort(split+1,end));
}

This works rather nicely. I have made some changes to the actual code over the above pseudo code to display interim results during the merge sort. The full code includes all the sorting routines we have done so far and the work on merge. Finally the code for the mergesort routine itself. It's implemented as a recursive routine as shown in the pseudocode.

The new routines I've added a new display(int[] array) method to display the new arrays that get built during the mergesort. I have also changed all 'for' statements to the for-each version where possible so you can compare it's use to a standard for loop in the previous implementation. I also use the 'display' methods where I can.

Final Code

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package apcompsci;

/**
 *
 * @author Nasty Old Dog
 */
public class SortLab {

    int[] labArray = null;
    int len = 10;

    public SortLab(int n) {
        this.len = n;
        labArray = new int[this.len];
        for (int i = 0; i < this.len; i++) {
            labArray[i] = i;
        }
        this.shuffle();
    }

    public SortLab() {
        this(10);
    }

    // This shuffle routine adapted from the work done previously
    private void shuffle() {
        int rindex;
        int swap;

        for (int i = 0; i < this.len; i++) {
            rindex = (int) ((Math.random() * ((double) (this.len - i))) + i);
            swap = this.labArray[i];
            this.labArray[i] = this.labArray[rindex];
            this.labArray[rindex] = swap;
        }
    }

    void swap(int k, int l) {
        int tmp;

        tmp = this.labArray[k];
        this.labArray[k] = this.labArray[l];
        this.labArray[l] = tmp;
    }

    public void display() {
        for (int i : this.labArray) {
            System.out.print(i + "  ");
        }
        System.out.println();
    }

    public void display(int[] array) {
        for( int i : array)
        {
            System.out.print(i + "  ");
        }
        System.out.println();
    }

    public void selection() {
        int tmp, tmp_idx;

        for (int i = 0; i < this.len - 1; i++) {
            //select the ith element save value and index
            tmp = this.labArray[i];
            tmp_idx = i;
            // Check if selected is the lowest of the remaining array
            // if not switch them
            for (int j = i + 1; j < this.len; j++) {
                if (this.labArray[j] < tmp) {
                    // found something less save it and it's index
                    tmp = this.labArray[j];
                    tmp_idx = j;
                }
            }
            // if tmp_idx != i then swap the values (move the lowest val in)
            if (tmp_idx != i) {
                this.labArray[tmp_idx] = this.labArray[i];
                this.labArray[i] = tmp;
            }
            System.out.print("interim:  ");
            this.display();
        }
    }

    // Alternate implementation of selection sort using swap function 
    public void selectionA() {
        int tmp, tmp_idx;
        for (int i = 0; i < this.len - 1; i++) {
            tmp = this.labArray[i];
            tmp_idx = i;
            for (int j = i + 1; j < this.len; j++) {
                if (this.labArray[j] < tmp) {
                    tmp = this.labArray[j];
                    tmp_idx = j;
                }
            }
            swap(i, tmp_idx);
            System.out.print("interim:  ");
            this.display();
        }
    }

    public void insertion() {
        int j;

        for (int i = 1; i < this.len; i++) {
            for (j = i; j > 0 && this.labArray[j] < this.labArray[j - 1]; j--) {
                this.swap(j, j - 1);
            }
            System.out.print("interim:  ");
            this.display();
        }
    }

    public void insertionShift()
    {
        int j;
        int tmp;

        for (int i = 1; i < this.len; i++) {
            // take ith element find where it should be inserted
            tmp = this.labArray[i];
            for (j = i; j > 0 && this.labArray[j] < this.labArray[j - 1]; j--) {
                // no need to do anything
                // when the loop ends j will be the insertion position
            }
            // Shift elements from j to i-1 over 1
            for (int k = i - 1; k >= j; k--)
            {
                this.labArray[k + 1] = this.labArray[k];
            }
            this.labArray[j] = tmp;
            System.out.print("interim:  ");
            this.display();
        }
    }

    public int[] merge(int[] a, int[] b)
    {
        int[] m = new int[a.length + b.length];
        int i=0;
        int j=0;

        for (int k = 0; k < m.length; k++)
        {
            if (i < a.length && j < b.length) {
            if (a[i]<=b[j]) {
                m[k] = a[i];
                i++;
            }
            else {
                m[k] = b[j];
                j++;
            }
            }
            else if (i < a.length) {  // b exhausted use up a
                m[k] = a[i];
                i++;
            }
            else { // b still has some left use up those
                m[k] = b[j];
                j++;
            }
        }
        return m;
    }

    public int[] mergesort(int begin, int end)
{
  int[] newArray = null;
  if (begin == end) { 
    // This is the end of the road create a new list of 1 element
    newArray = new int[1];
    newArray[0] = this.labArray[begin];
  System.out.print("interim:  ");
  this.display(newArray);
    return newArray;
  }
  if (1 == end-begin) {
    // down to 2 elements 
    newArray = new int[2];
    if ( this.labArray[begin] < this.labArray[end]) {
      newArray[0] = this.labArray[begin];
      newArray[1] = this.labArray[end];
    } else {
      newArray[0] = this.labArray[end];
      newArray[1] = this.labArray[begin];
    }
  System.out.print("interim:  ");
  this.display(newArray);
    return newArray;
  }
  int split = (begin + end)/2;
  newArray = this.merge(this.mergesort(begin, split), this.mergesort(split+1,end));
  System.out.print("interim:  ");
  this.display(newArray);
  return newArray;
}


    public static void main(String[] args) {
        SortLab select = new SortLab();
        SortLab selectA = new SortLab();
        SortLab insert = new SortLab();
        SortLab insertA = new SortLab();
        SortLab msort = new SortLab();

        System.out.println("Selection Sort");
        System.out.print("unsorted: ");
        select.display();
        select.selection();
        System.out.print("sorted:   ");
        select.display();
        System.out.println("SelectionA Sort");
        System.out.print("unsorted: ");
        selectA.display();
        selectA.selectionA();
        System.out.print("sorted:   ");
        selectA.display();
        System.out.println();
        System.out.println();
        System.out.println("Insertion Sort");
        System.out.print("unsorted: ");
        insert.display();
        insert.insertion();
        System.out.print("sorted:   ");
        insert.display();
        System.out.println("Insertion Sort with Explicit Shift");
        System.out.print("unsorted: ");
        insertA.display();
        insertA.insertion();
        System.out.print("sorted:   ");
        insertA.display();
        System.out.println("\n");
        System.out.println("Merge Testing");
        int[] l1 = {0, 2, 3, 4, 6, 7, 9};
        int[] l2 = {1, 3, 5, 8, 10};
        int[] l3 = msort.merge(l1,l2);
        System.out.print("l1 = ");
        msort.display(l1);
        System.out.print("l2 = ");
        msort.display(l2);
        System.out.print("l3 = merge(l1,l2) = ");
        msort.display(l3);
        System.out.println("\n");

        System.out.println("merge sort");
        System.out.print("unsorted: ");
        msort.display();
        int[] sorted  = msort.mergesort(0,msort.len-1);
        System.out.print("sorted:   ");
        msort.display(sorted);
    }
}

Output 2

run:
Selection Sort
unsorted: 6  2  5  0  3  8  7  1  4  9  
interim:  0  2  5  6  3  8  7  1  4  9  
interim:  0  1  5  6  3  8  7  2  4  9  
interim:  0  1  2  6  3  8  7  5  4  9  
interim:  0  1  2  3  6  8  7  5  4  9  
interim:  0  1  2  3  4  8  7  5  6  9  
interim:  0  1  2  3  4  5  7  8  6  9  
interim:  0  1  2  3  4  5  6  8  7  9  
interim:  0  1  2  3  4  5  6  7  8  9  
interim:  0  1  2  3  4  5  6  7  8  9  
sorted:   0  1  2  3  4  5  6  7  8  9  
SelectionA Sort
unsorted: 0  3  1  6  9  5  8  4  2  7  
interim:  0  3  1  6  9  5  8  4  2  7  
interim:  0  1  3  6  9  5  8  4  2  7  
interim:  0  1  2  6  9  5  8  4  3  7  
interim:  0  1  2  3  9  5  8  4  6  7  
interim:  0  1  2  3  4  5  8  9  6  7  
interim:  0  1  2  3  4  5  8  9  6  7  
interim:  0  1  2  3  4  5  6  9  8  7  
interim:  0  1  2  3  4  5  6  7  8  9  
interim:  0  1  2  3  4  5  6  7  8  9  
sorted:   0  1  2  3  4  5  6  7  8  9  


Insertion Sort
unsorted: 1  3  2  7  6  0  9  8  5  4  
interim:  1  3  2  7  6  0  9  8  5  4  
interim:  1  2  3  7  6  0  9  8  5  4  
interim:  1  2  3  7  6  0  9  8  5  4  
interim:  1  2  3  6  7  0  9  8  5  4  
interim:  0  1  2  3  6  7  9  8  5  4  
interim:  0  1  2  3  6  7  9  8  5  4  
interim:  0  1  2  3  6  7  8  9  5  4  
interim:  0  1  2  3  5  6  7  8  9  4  
interim:  0  1  2  3  4  5  6  7  8  9  
sorted:   0  1  2  3  4  5  6  7  8  9  
Insertion Sort with Explicit Shift
unsorted: 7  1  2  5  4  3  6  9  8  0  
interim:  1  7  2  5  4  3  6  9  8  0  
interim:  1  2  7  5  4  3  6  9  8  0  
interim:  1  2  5  7  4  3  6  9  8  0  
interim:  1  2  4  5  7  3  6  9  8  0  
interim:  1  2  3  4  5  7  6  9  8  0  
interim:  1  2  3  4  5  6  7  9  8  0  
interim:  1  2  3  4  5  6  7  9  8  0  
interim:  1  2  3  4  5  6  7  8  9  0  
interim:  0  1  2  3  4  5  6  7  8  9  
sorted:   0  1  2  3  4  5  6  7  8  9  


Merge Testing
l1 = 0  2  3  4  6  7  9  
l2 = 1  3  5  8  10  
l3 = merge(l1,l2) = 0  1  2  3  3  4  5  6  7  8  9  10  


merge sort
unsorted: 6  9  0  8  7  2  3  1  4  5  
interim:  6  9  
interim:  0  
interim:  0  6  9  
interim:  7  8  
interim:  0  6  7  8  9  
interim:  2  3  
interim:  1  
interim:  1  2  3  
interim:  4  5  
interim:  1  2  3  4  5  
interim:  0  1  2  3  4  5  6  7  8  9  
sorted:   0  1  2  3  4  5  6  7  8  9  
BUILD SUCCESSFUL (total time: 2 seconds)

Conclusion

If you haven't done so already you should at the very least download the AP Computer Science A Course Description. It's a PDF file and basically goes over everything you should have been taught in AP Computer Science (See References). My read of the latest 2010 document indicates that you only need to know about the 3 sorts I have covered. However in years past looking at the teaching site Bubble sort and Quick sort have been taught in the past. If you have time go over those your teacher's may have introduced them to you. If not then take the College Board at their word and make sure you know the 3 I have presented. For Future knowledge Donald Knuth in his Art of Computer Programming series goes over the following sorts (based on a quick scan of the text I may have missed one or two):

• Insertion sort
• Shell Sort
• Exchange Sort
• Bubble Sort
• Baucher Sort
• Quick Sort
• Heap Sort
• Merge Sort

If you go online to Google Scholar you will find many more. Sorting is certainly a basic problem for any Computer Scientist. They all have their drawbacks and the best one changes from time to time as people discover scenarios where the algorithms don't work well. In my day of learning this material I was told that Quicksort was best in actual practice even though theoretically Heap sort should have the better outcome. I don't have a reference for you but if you continue your pursuit of computers you will probably come across Journal articles that will espouse one algorithm over another.

References

1. Knuth, Donald Ervin. The Art of Computer Programming Sorting and Searching. 2nd ed. Vol. 3. Reading, Mass. Addison-Wesley, 1998.
2. https://apstudent.collegeboard.org/apcourse/ap-computer-science-a/course-details "Course Details." AP Computer Science A. N.p., n.d. Web. 29 Mar. 2013.

Author: Nasty Old Dog

More Recursion

Double Recursion

Introduction

Recursion is a wonderful thing once you've mastered it. There are often problems in Computer Science that have simple, concise solutions once recursion is applied to the problem. One of the biggest problem for beginners occurs when they try to follow the recursive calls of a routine that makes two or more calls to itself. The problem becomes evident in what I term a double recursion. Once you understand how to trace the calls in this type of routine you will be able to apply the analysis to any number of calls.

What exactly is a double recursion? It's a method that calls itself twice. This is different from a method that chooses one type of recursive call over another. In this case every call to the method will spawn 2 more calls to the method. This then recurses down spawning 2 more calls until the test case is met and the method calls start to return back up the chain. The problem for the beginning student is that this type of arrangement maps out a 'tree' of calls and the student must perform a manual 'depth' first search of the call tree.

Trees

Trees are a data structure object that crop up in computer science and while it is not necessary to program one for the AP Computer Science exam a brief description of terminology for trees is useful to the discussion here. Students when trying to figure out a double recursion forget about what the computer is doing and bounce back and forth between a 'depth' first search of the method calls and what is know as a 'breadth' first search.

A diagram will explain this much better than words.

Depth First Search

In a depth search first you must follow the branches all the way down then go back up and follow any other branches etc. The numbering of the boxes shows how we visit the nodes. This is the same for recursion when 2 or more recursive calls are made. You must follow the first recursive trail and then back up and follow the next call in a similar fashion to this tree.

Breadth First Search

The mistake is to try to account for both calls at the same time when you enter the first call sequence. The computer doesn't do it this way it blindly follows the trail of the first call then when it comes back it handles the second. So breadth first search is a mistake of reading the program as you would a story. You complete the paragraph then go off to see what the next sequence is. The following diagram is the WRONG way to follow a recursion tree:

I almost don't want to show you this for fear you will worry about it. But rememeber you must follow the first call sequence down until the test case is reached. Then you pop back up at each stage to handle the second call. Forget about breadth first and stick to the order of the first diagram. Recursion is naturally a depth first search.

Make the computer do it

While you must learn to draw out the call structure by hand. There is no reason not to experiment with having the computer do it for you. With the appropriate use of output statements and a little bookkeeping in a program example we can make the computer account for how the recursion is happening. First let's create a single recursive method that logs it's calls then we can add a double recursion to the example. In the end you will have a program that maps out it's call tree in a textual representation. From there you only need to be able to draw a sketch on the test and you should be ready for any recursive problem thrown at you.

class DoubleRecurse {

    public static void singleRecursion(int[] vals, int m) {
        if (m >= 0) {
            System.out.print(vals[m] + "  ");
            singleRecursion(vals, m - 1);
        }
    }

    public static void main(String[] args) {
        int[] myArray = {5, 4, 3, 2, 1, 0};

        singleRecursion(myArray, myArray.length-1);
        System.out.println();
    }
}

Output

run:
0  1  2  3  4  5  
BUILD SUCCESSFUL (total time: 0 seconds)

So the code goes to the end of the array and prints each value. This reverses the order of the array. This is because the print happens before the recursive call back into singleRecursion. If the print statement is moved to after the method call the recursion goes all the way to m = -1 which ends the recursion then as the computer starts to come back up from it's decent into the recursion values will be printed in normal order indexed from 0 - 5 to print the values as they appear in the intialization of myArray.

Here is the class with the print statement moved after the recursive call:

class DoubleRecurse {

    public static void singleRecursion(int[] vals, int m) {
        if (m >= 0) {
            singleRecursion(vals, m - 1);
            System.out.print(vals[m] + "  ");
        }
    }

    public static void main(String[] args) {
        int[] myArray = {5, 4, 3, 2, 1, 0};

        singleRecursion(myArray, myArray.length-1);
        System.out.println();
    }
}

Output 1

run:
5  4  3  2  1  0  
BUILD SUCCESSFUL (total time: 1 second)

Exposing Recursion

Let's add some print statements to expose the recursion more explicitly in the output. One way to display the recursion is to present the output from each call on a separate line. By using field variables we can also track the number of calls and the depth (or level) of the recursion. The depth field can be used to prepend spaces so that deeper levels of recursion are indented in the output.

The changes will include making this object oriented by taking away the static method and making it a plain method call to singleRecursion. This will mean that a DoubleRecurse object needs to be instantiated in the main method so the method can be used. But it means that the new fields will be available for any new recursive methods added to the class. The new code with the tracking fields and the new output statements follows:

class DoubleRecurse {
    // Track number of calls
    int calls = 0;
    // Track level
    int depth = 0;

    void indent(int spaces)
    {
        for (int i = 0; i < spaces; i++) {
            System.out.print("  ");
        }
    }

    public void singleRecursion(int[] vals, int m) {
        calls++;
        depth++;

        // track calls depth and m
        indent(depth);
        System.out.println("calls = " + calls 
                + "  depth = " + depth 
                + "  m = " + m);

        if (m >= 0) {
            singleRecursion(vals, m - 1);
            indent(depth);
            System.out.println(vals[m]);
        }
        else {
            indent(depth);
            System.out.println("test case met no more recursion start backing out");
        }

        depth --;
    }

    public static void main(String[] args) {
        DoubleRecurse recursion = new DoubleRecurse();
        int[] myArray = {5, 4, 3, 2, 1, 0};

        recursion.singleRecursion(myArray, myArray.length-1);
        System.out.println();
    }
}

Output 2

run:
  calls = 1  depth = 1  m = 5
    calls = 2  depth = 2  m = 4
      calls = 3  depth = 3  m = 3
        calls = 4  depth = 4  m = 2
          calls = 5  depth = 5  m = 1
            calls = 6  depth = 6  m = 0
              calls = 7  depth = 7  m = -1
              test case met no more recursion start backing out
            5
          4
        3
      2
    1
  0

BUILD SUCCESSFUL (total time: 0 seconds)

Double Recursion

Now that there are tools to display the recursive calls, the program can be modified to track a doubly recursive call. Rather than change the singleRecursion method a new method called doubleRecursion can be added.

In the new code there are 4 method calls. The original singleRecursion method that does no tracking. A new method called singleRecursionTrack that has the tracking fields and output statements. Then the single recursion modified to do double recursion and it's tracking counterpart named doubleRecursion and doubleRecursionTrack respectively

class DoubleRecurse {
    // Track number of calls
    int calls = 0;
    // Track level
    int depth = 0;

    void indent(int spaces)
    {
        for (int i = 0; i < spaces; i++) {
            System.out.print("  ");
        }
    }

    public void singleRecursion(int[] vals, int m) {        
        if (m >= 0) {
            singleRecursion(vals, m - 1);
            System.out.print(vals[m] + "  ");
        }
    }

    public void singleRecursionTrack(int[] vals, int m) {
        this.calls++;
        this.depth++;

        // track calls depth and m
        indent(this.depth);
        System.out.println("calls = " + this.calls 
                + "  depth = " + this.depth 
                + "  m = " + m);

        if (m >= 0) {
            singleRecursionTrack(vals, m - 1);
            indent(this.depth);
            System.out.println(vals[m]);
        }
        else {
            indent(this.depth);
            System.out.println("test case met no more recursion start backing out");
        }

        this.depth--;
    }

    public void doubleRecursion(int[] vals, int m) {        
        if (m >= 0) {
            this.doubleRecursion(vals, m - 1);
            System.out.print(vals[m] + "  ");
            this.doubleRecursion(vals, m - 3);
        }
    }

    public void doubleRecursionTrack(int[] vals, int m) {
        this.calls++;
        this.depth++;

        // track calls depth and m
        indent(this.depth);
        System.out.println("calls = " + this.calls 
                + "  depth = " + this.depth 
                + "  m = " + m);

        if (m >= 0) {
            this.doubleRecursionTrack(vals, m - 1);
            indent(this.depth);
            System.out.println(vals[m]);
            this.doubleRecursionTrack(vals, m - 3);
        }
        else {
            indent(this.depth);
            System.out.println("test case met no more recursion start backing out");
        }

        this.depth --;
    }


    public static void main(String[] args) {
        DoubleRecurse recursion = new DoubleRecurse();
        int[] myArray = {5, 4, 3, 2, 1, 0};

        recursion.singleRecursion(myArray, myArray.length-1);
        System.out.println();
        recursion.singleRecursionTrack(myArray, myArray.length-1);
        System.out.println();
        recursion.calls = 0;  // start new recursion reset calls to track
        recursion.doubleRecursion(myArray, myArray.length-1);
        System.out.println();
        recursion.doubleRecursionTrack(myArray, myArray.length-1);
        System.out.println();
    }
}

Output 3

run:
5  4  3  2  1  0  
  calls = 1  depth = 1  m = 5
    calls = 2  depth = 2  m = 4
      calls = 3  depth = 3  m = 3
        calls = 4  depth = 4  m = 2
          calls = 5  depth = 5  m = 1
            calls = 6  depth = 6  m = 0
              calls = 7  depth = 7  m = -1
              test case met no more recursion start backing out
            5
          4
        3
      2
    1
  0

5  4  3  2  5  1  5  4  0  5  4  3  
  calls = 1  depth = 1  m = 5
    calls = 2  depth = 2  m = 4
      calls = 3  depth = 3  m = 3
        calls = 4  depth = 4  m = 2
          calls = 5  depth = 5  m = 1
            calls = 6  depth = 6  m = 0
              calls = 7  depth = 7  m = -1
              test case met no more recursion start backing out
            5
              calls = 8  depth = 7  m = -3
              test case met no more recursion start backing out
          4
            calls = 9  depth = 6  m = -2
            test case met no more recursion start backing out
        3
          calls = 10  depth = 5  m = -1
          test case met no more recursion start backing out
      2
        calls = 11  depth = 4  m = 0
          calls = 12  depth = 5  m = -1
          test case met no more recursion start backing out
        5
          calls = 13  depth = 5  m = -3
          test case met no more recursion start backing out
    1
      calls = 14  depth = 3  m = 1
        calls = 15  depth = 4  m = 0
          calls = 16  depth = 5  m = -1
          test case met no more recursion start backing out
        5
          calls = 17  depth = 5  m = -3
          test case met no more recursion start backing out
      4
        calls = 18  depth = 4  m = -2
        test case met no more recursion start backing out
  0
    calls = 19  depth = 2  m = 2
      calls = 20  depth = 3  m = 1
        calls = 21  depth = 4  m = 0
          calls = 22  depth = 5  m = -1
          test case met no more recursion start backing out
        5
          calls = 23  depth = 5  m = -3
          test case met no more recursion start backing out
      4
        calls = 24  depth = 4  m = -2
        test case met no more recursion start backing out
    3
      calls = 25  depth = 3  m = -1
      test case met no more recursion start backing out

BUILD SUCCESSFUL (total time: 0 seconds)

This gives a good trail of when calls take place and at what level but it is still not completely obvious when the first recursive call is taking place and when the second is. By adding a field to the doubleRecursion the call number can be saved separately from the total calls. Adding 2 printlns before the calls (indenting for the current depth of course) now highlights exactly where the processing is being done.

public void doubleRecursionTrack(int[] vals, int m) {
    int current_call = 0;

    this.calls++;
    current_call = this.calls;
    this.depth++;

    // track calls depth and m
    indent(this.depth);
    System.out.println("calls = " + this.calls 
            + "  depth = " + this.depth 
            + "  m = " + m);

    if (m >= 0) {
        indent(this.depth);
        System.out.println("call = " + current_call + " enter first recursion");
        this.doubleRecursionTrack(vals, m - 1);
        indent(this.depth);
        System.out.println(vals[m]);
        indent(this.depth);
        System.out.println("call = " + current_call + " enter second recursion");
        this.doubleRecursionTrack(vals, m - 3);
    }
    else {
        indent(this.depth);
        System.out.println("test case met no more recursion start backing out");
    }

    this.depth --;
}

Output 3

run:
5  4  3  2  1  0  
  calls = 1  depth = 1  m = 5
    calls = 2  depth = 2  m = 4
      calls = 3  depth = 3  m = 3
        calls = 4  depth = 4  m = 2
          calls = 5  depth = 5  m = 1
            calls = 6  depth = 6  m = 0
              calls = 7  depth = 7  m = -1
              test case met no more recursion start backing out
            5
          4
        3
      2
    1
  0

5  4  3  2  5  1  5  4  0  5  4  3  
  calls = 1  depth = 1  m = 5
  call = 1 enter first recursion
    calls = 2  depth = 2  m = 4
    call = 2 enter first recursion
      calls = 3  depth = 3  m = 3
      call = 3 enter first recursion
        calls = 4  depth = 4  m = 2
        call = 4 enter first recursion
          calls = 5  depth = 5  m = 1
          call = 5 enter first recursion
            calls = 6  depth = 6  m = 0
            call = 6 enter first recursion
              calls = 7  depth = 7  m = -1
              test case met no more recursion start backing out
            5
            call = 6 enter second recursion
              calls = 8  depth = 7  m = -3
              test case met no more recursion start backing out
          4
          call = 5 enter second recursion
            calls = 9  depth = 6  m = -2
            test case met no more recursion start backing out
        3
        call = 4 enter second recursion
          calls = 10  depth = 5  m = -1
          test case met no more recursion start backing out
      2
      call = 3 enter second recursion
        calls = 11  depth = 4  m = 0
        call = 11 enter first recursion
          calls = 12  depth = 5  m = -1
          test case met no more recursion start backing out
        5
        call = 11 enter second recursion
          calls = 13  depth = 5  m = -3
          test case met no more recursion start backing out
    1
    call = 2 enter second recursion
      calls = 14  depth = 3  m = 1
      call = 14 enter first recursion
        calls = 15  depth = 4  m = 0
        call = 15 enter first recursion
          calls = 16  depth = 5  m = -1
          test case met no more recursion start backing out
        5
        call = 15 enter second recursion
          calls = 17  depth = 5  m = -3
          test case met no more recursion start backing out
      4
      call = 14 enter second recursion
        calls = 18  depth = 4  m = -2
        test case met no more recursion start backing out
  0
  call = 1 enter second recursion
    calls = 19  depth = 2  m = 2
    call = 19 enter first recursion
      calls = 20  depth = 3  m = 1
      call = 20 enter first recursion
        calls = 21  depth = 4  m = 0
        call = 21 enter first recursion
          calls = 22  depth = 5  m = -1
          test case met no more recursion start backing out
        5
        call = 21 enter second recursion
          calls = 23  depth = 5  m = -3
          test case met no more recursion start backing out
      4
      call = 20 enter second recursion
        calls = 24  depth = 4  m = -2
        test case met no more recursion start backing out
    3
    call = 19 enter second recursion
      calls = 25  depth = 3  m = -1
      test case met no more recursion start backing out

BUILD SUCCESSFUL (total time: 2 seconds)

Conclusion

This should help when trying to follow recursion. Certainly in an exam situation they don't allow an IDE to code with, but with some paper, pencil and a little fortitude even the average student should be able to build a recursion tree by hand. The AP question makers understand there is limited time so the example provided here is much more complex in terms of the number of calls a student will have to track.

A study recommendation
If you find yourself getting the recursion problems wrong in your practice tests, code them up with indentation and tracking information. Most likely you are making a simple mistake drawing out the call tree. The output from your code should enlighten you on the proper call pattern.

Date: 2013-03-26T16:55-0400

Author: Nasty Old Dog

Recursion

In the beginning there was the SUBROUTINE.

In the early days of programming there were no large standard libraries available. There were a small set of routines that gave the programmer access to operating system facilities like printers and screen output. In some languages these were built right into the language, much the way Java has some built in constructs for the String class.

In assembly language programming, a language to code directly in the codes the CPU (Central Processing Unit) understands, there is a 'JSR' statement. 'JSR' is a mneumonic that stands for Jump SubRoutine. In an assembler language program this means to jump to a 'label' placed in your code then, return when the 'RET' statement is hit. Return to where? To the statement right after the 'JSR'. It's much like when your playing a video game and your mom asks you to do the dishes or take out the garbage. You, as your very own CPU, pause the video game, go and accomplish the chore, then return right back at the video game picking up exactly where you left off. The problem for the assmebly language programmer is that these statements do not allow parameters. The programmer must take care of all of that themselves in the assembly language code

FORTRAN was one of the very first computer languages developed. It's short for Formula Translation. It's big claim to fame was to provide the user with variables and arithmetic operators built into the language. This became a main stay of Engineers and Scientists who wanted to solve difficult mathmatical problems. Fortran also provided a feature called SUBROUTINEs. It had a SUBROUTINE statement and better than it's assembly language counterpart it allowed you to define parameters and use them in your programs. In fact there is not much difference between the look of a FORTRAN SUBROUTINE and a Java method. Java is a little fancier there are 'public' and 'private' methods. There are 'static' methods. In the early days of FORTRAN you didn't have to worry about this every SUBROUTINE was 'static' SUBROUTINEs never return a value because FORTRAN had FUNCTION statements for that.

FORTRAN also had a CALL statement so you could execute your SUBROUTINE. This is why you may hear people talk about a 'Method Call' or an instructor may say "Don't for get to call your method". Computer Science has a very informal language when we talk about various topics, but we try to use different terminology when we can to better describe what we are doing. The example here is that I may tell you to 'Run' your method and you may understand what I mean. But more formally you 'Run' a program and the program 'Calls' your method.

A SUBROUTINE can call other SUBROUTINEs

The whole point of this stroll down memory lane is that once the syntax of the subroutine became establised, there was a natural inclination to allow a SUBROUTINE to call itself. We already had recursive definitions as part of mathematics. So now that we have computers that animate our mathematics for us, the push for recursive SUBROUTINEs was on.

It may seem that it should be self-evident that a SUBROUTINE can call itself but in the early design of computer languages it turns out you must do some special things under the covers to get this to happen. So newer languages that followed after FORTRAN made sure they had these capabilities. I won't bore you with a cronology of how recursion came into being. There were languages in existance at the time of FORTRAN that already had it. But suffice it to say that when Personal Computers came about and the C language (a predecessor to Java) dominated the programming of that platform, C had built in recursion. Lucky for you! because it's a pain to simulate recursion in a language that doesn't have it. Java as an ancestor of C also has recursion built in.

METHODS ARE JAVA SUBROUTINES

As languages change so does the nomenclature. SUBROUTINEs are now methods. Methods don't even have a METHOD statement like SUBROUTINES do. This is because after people became very familiar with FORTRAN they realized that a SUBROUTINE definition can be recognized by:

• it's name
• the parenthesis that follow
• and the parameter definitions inside the parenthesis

So by the time Java comes around we expect you as a newbie just to pick up on this on your own. If you are an older programmer you know you got sick of writing SUBROUTINE for each and every SUBROUTINE definition. That's a large amount of typing saved (well kind of there are things like public and void but they are much shorter words. We even dropped a formal statement for calling the SUBROUTINE. Now you are just supposed to know that any name followed by parenthesis with comma separated parameters is a Method call. Methods have all the stuff of a subroutine but now are grouped into objects (ie. class definitions). They can be inherited and they can be overridden. These are certainly things that don't happen with SUBROUTINES. The name change is fitting since the old fashioned SUNROUTINES have more in common with "static" methods than with methods in general.

METHODS can call themselves

Recursion being well established in computer science methods can call themselves, it's built in to the language. The danger of course is that the programmer must make sure they have accounted for any and all 'base' cases, otherwise the code will run forever! Well, not forever you eventually run out of memory.

Recursive definitions

The first example is always factorial. Sorry about that. But it has a simply stated recursive definition so it is popular. Students usually focus on factorial being so trivial to implement that they feel recursion is senseless since you could do it easily with a loop. But like so many things in computer science the trivial case is foreshadowing of more complicated stuff yet to come.

Factorial

factorial (n) = 1 (for n = 1)

                   = factorial(n-1) * n (for n > 1)

Fibonacci numbers

Fib(n) = 0 (for n = 0)

           = 1 (for n = 1)

           = Fib(n-1) + Fib(n-2) (for n > 1)

This is a better example for recursion. It does not have a trivial loop alternative. That's not to say you can't create a loop that can do it. Every recursive implementation has a looping counterpart. It's just that it's not trivial like factorial is. The double calls to Fib above do us in for coming up with an easy looping code design.

This type of recursion is termed tree recursion by Abelson and Sussman in their classic work "Structure and Interpretation of Computer Programs"(known in computer science circles as just SICP). That's because if you were to draw out all the recursive calls at each step, you would form an inverted tree with the first call leading to 2 calls and those two calls lead to two calls and so on.

Greatest Common Divisors

Given 2 integers this is the greatest integer that divides both of them evenly. It is very helpful when you are trying to reduce fractions to lowest terms.

Gcd(a,b) = a (for b = 0)

             = Gcd (b, remainder(a,b)) (for b > 0)

If you think the above definition is some modern mathematic torture dreamed up to make your life a living hell. Abelson and Sussman point out that the above definition appears in Euclid's Elements Book 7 circa 300 BC. So the reality is that mathematicians have been developing torturous problems for their students from time immemorial.

Your Job

I leave it up to the student to implement these functions. If your interested there are more recursive functions defined in the SICP which is available online. There are also Scheme Programming Language examples of their implementation. That may assist you with the Java implementation or it may confuse you more.

Princeton University has an excellent collection of recursive functions at their introduction to computer science web site. Their site includes a large number of implementation examples. I would suggest you try to implement the examples above and then visit their site if you have any problems. http://introcs.cs.princeton.edu/java/23recursion/ The link to Princeton's course is here: http://introcs.cs.princeton.edu/java/home/ This includes a much broader perspective also going over some computer architecture which I believe is incredibly helpful when you are trying to make sense of computer science in general.

What No Code?

Of course there is code. It wouldn't be a comp sci article without code. Using our previously defined APString class I will implement a reverse method that uses recursion to reverse the elements of our string. Now, because we have no built in operators for the APString class (such as string concatenation), we can't do a simple recursive routine that's possible with the Java String class. Actually that's a good idea let's first look at using recursion with the Java String class.

A simple recursive methodology for Java Strings would be the following:

1. take the first character of the String and store it as a string
2. reverse the rest of the string after the first character is removed
3. concatenate the new reversed remainder with the first character added to the end.

Step 2 has the recursion in it if I name the method 'revStr' the pseudo code will look like:

String firstch;
String restStr;

// ignore the base case for now
firstch = str.subString(1,2);
restStr = str.subString(2);
return revStr(restStr) + firstch;  // concatenate the first character onto the end of the string

Take some time to think of what the base case is for the code fragment above. I went ahead and implemented the whole code and placed it at the end of the article but given what I have done above you should be able to code the whole thing yourself. Go ahead and see if you can reverse a Java string recursively in your own Java IDE. I would create a separate class for this assignment and give it it's own main method. Then once you have it working compare it to the code at the end of the article.

APString reverse done recursively

This was not such an obvious recursion because there are no built in facilities for APString like the concatenation operator that the Java String has. We have not even implemented a concatenation method or a substring method. So you can see the time savings that Java provides and the difficulty we have trying to duplicate the same functionality in a class of our own. I will add those in a future article and try to implement reverse as we did for the Java String class.

Since we don't have the benefit of the methods described above I will take advantage of a Java method for arrays.

Arrays.copyOfRange(<array variable name>, start index, end index).

This is provided by the Java class library. It's kind of cheating because I don't have to make my own copy routine, which would probably loop through all the elements of the array. Since we have to loop why bother reversing the string recursively other than to show how you can think of problems recursively? Well, that's the point really. There are times when a looping construct is the best mechanism but there are times when recursion will help to simplify your code. Most of the time you will have to try both and see which one provides you with an elegant solution.

Design of the recursive algorithm

The APString class uses char arrays to implement it's String functionality. We will need a temporary char array to hold the reversed elements and to be our working storage as we change the order of the characters. We could do this in the char array we use for the object itself but then this would actually change our object rather than providing a new object with the desired results. This also means we need to return an object of APString as the final result. This creates a problem for recursion because I want to recurse on the char array and then return an APString when all is done.

• Design Requirements
  1. return an object of APString
  2. create a recursive routine to recurse on char array
  3. use a temporary char array to be the working storage
  4. Don't let any of our methods change the underlying values of our original APString object

This means we will need 2 methods instead of one. One method to setup our working storage and return an APString value and another method to do the recursion on our working storage.

Recursive method and setup method

// reverse_array recursive helper procedure for reverser
// 
private void reverse_array(int startIdx, int endIdx, char ch[]) 
{   
    char tmpch;
    // base case 1: odd length we have reached the middle element
    if (startIdx == endIdx) 
        return;
    // base case 2: even length array the indexes are side by side
    if ((endIdx-startIdx) == 1) 
    {
        tmpch = ch[startIdx];
        ch[startIdx] = ch[endIdx];
        ch[endIdx] = tmpch;
        return;
    }
    // recursive case swap current indexes then recurse on the rest
    tmpch = ch[startIdx];
    ch[startIdx] = ch[endIdx];
    ch[endIdx] = tmpch;
    reverse_array(startIdx+1,endIdx-1,ch);        
}

 // The intial call to set up the recursive routine above with working storage array
public APString revStr() {
    char[] tmparray = Arrays.copyOfRange(chArray, 0, this.length());
    reverse_array(0,this.length()-1,tmparray);
    return new APString(tmparray);
}

The main method used to test the above code

public static void main(String[] args) {
    // Since we are trying to avoid the use of the built-in Java Strings
    // we are forced to define strings by initializing a char array
    // I think you can see why it's so nice to have Strings built into
    // Java. Imagine having to define every string like this:
    char[] a = {'T','h','i','s',' ','i','s',' ','a',' ','t','e','s','t','\0'};
    APString ap = new APString(a);
    // Using the String double quotes built in the following is an equivalent
    // statement:
    APString ap1 = new APString("This is a test".toCharArray());

    System.out.println(ap.toString()+ "   length = " + ap.length());
    System.out.println(ap1.toString()+ "   length = " + ap1.length());
    System.out.println(ap.reverse().toString());
    System.out.println(ap.revStr().toString());
    System.out.println("No change to original: " + ap.toString());
}

And the output from testing:

run:
This is a test   length = 14
This is a test   length = 14
Looping reverse: tset a si sihT
Recursive reverese: tset a si sihT
No change to original: This is a test
BUILD SUCCESSFUL (total time: 0 seconds)

The whole APString code with the recursive procedures built in

/*
 * APString class
 * The idea is to create a string class that uses arrays to hold the characters
 * This methodology is closer to how the actual hardware is organized.
 * The String class in Java has built in support. In fact any double quoted 
 * String is itself a String class object. "a string".toString(); is valid
 * Java code and all of the methods of the String class may be used above
 * in place of toString().
 * 
 * Java hides much of this organization because it is object oriented and 
 * there is a long history of String operations in computer science. So the
 * designers (rightly so) added String handling capabilities in the language 
 * itself. However for people trying to learn about computers for the first
 * time this shielding (known in computer science terms as abstracting) of the
 * lower level organization is a disservice. While Strings are well known the 
 * patterns of their processing are repeated enough for other things that a 
 * thorough understanding of the low level processing of Strings will only help
 * the new Programmer/Computer Scientist.
 * 
 * Indeed Donald Knuth in his classic treatise "The Art of Computer Programming"
 * goes so far as to invent a ficticious computer with a ficticious 
 * assembly language to bring to light the issues of computer architecture and
 * their effect on the design of computer programs.
 */
package apcompsci;

import java.util.Arrays;

/**
 *
 * @author nasty
 */
public class APString {    
    // It's not necessary to limit a char array like this. Java will 
    // dynamically create space as needed but in some computer languages
    // they must be allocated out ahead of time. So as a place holder we
    // define our initial array as 100 chars.
    char chArray[] = new char [100];
    int len;

    APString(char chArray[])
    {
        // Let's copy the char array given into the one we defined above as
        // part of the class
        int i = 0;
        for(i = 0; i < chArray.length; i++)
          this.chArray[i] = chArray[i];
        this.len = i;
        this.chArray[i]='\0';
        // The above '\0' is the ASCII null character. By setting the very
        // last character to this value it acts as a flag to let us know
        // we are at the end of our string. The length() method uses this to
        // calculate the length of the string
        // I also implemented a len field to store this in. It is left to 
        // the reader to reimplement this class with a length field and get
        // get rid of the null termination. This would save a lot of looping
        // over the string to get the string length
    }

// All classes defined in Java have a base toString but because we have
// defined some fields as part of our class we need to convert those to 
// Strings so we can print them out and we override the base toString features
//
// It's unfortunate but we must rely on the built-in String class because
// they are used by all the print procedures
@Override
    public String toString()
    {
        String s = "";

        for (int i = 0; i < this.len; i++)
            s = s + this.chArray[i];
        return s;
    }

    public int length()
    {
        int i = 0;
        for (i = 0; this.chArray[i] != '\0'; i++)
        {
            // Do nothing just let i keep count and keep looping until we hit
            // the null character which will break the test above
        }
        return i;
    }

    // reverse - create a new APString that reverses all the characters in 
    // the current class. Except for the null string we don't want that to 
    // be our first character. WHY?
    public APString reverse()
    {
        char tmp[] = new char[this.length() + 1];
        int j = 0;
        for (int i = this.length() - 1; i >= 0; i-- , j++)
        {
            tmp[j] = this.chArray[i];
        }
        tmp[j] = '\0';
        return new APString(tmp);
    }

    // reverse_array recursive helper procedure for reverser
    // 
    private void reverse_array(int startIdx, int endIdx, char ch[]) 
    {   
        char tmpch;
        // base case 1: odd length we have reached the middle element
        if (startIdx == endIdx) 
            return;
        // base case 2: even length array the indexes are side by side
        if ((endIdx-startIdx) == 1) 
        {
            tmpch = ch[startIdx];
            ch[startIdx] = ch[endIdx];
            ch[endIdx] = tmpch;
            return;
        }
        // recursive case swap current indexes then recurse on the rest
        tmpch = ch[startIdx];
        ch[startIdx] = ch[endIdx];
        ch[endIdx] = tmpch;
        reverse_array(startIdx+1,endIdx-1,ch);        
    }

     // The intial call to set up the recursive routine above with working storage array
    public APString revStr() {
        char[] tmparray = Arrays.copyOfRange(chArray, 0, this.length());
        reverse_array(0,this.length()-1,tmparray);
        return new APString(tmparray);
    }

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // Since we are trying to avoid the use of the built-in Java Strings
        // we are forced to define strings by initializing a char array
        // I think you can see why it's so nice to have Strings built into
        // Java. Imagine having to define every string like this:
        char[] a = {'T','h','i','s',' ','i','s',' ','a',' ','t','e','s','t','\0'};
        APString ap = new APString(a);
        // Using the String double quotes built in the following is an equivalent
        // statement:
        APString ap1 = new APString("This is a test".toCharArray());

        System.out.println(ap.toString()+ "   length = " + ap.length());
        System.out.println(ap1.toString()+ "   length = " + ap1.length());
        System.out.println("Looping reverse: " + ap.reverse().toString());
        System.out.println("Recursive reverese: " + ap.revStr().toString());
        System.out.println("No change to original: " + ap.toString());
    }
}

Recursive reverse on the Java String class

package apcompsci;

/**
 *
 * @author Nasty Old Dog
 */
public class NODString {
    public String revStr(String s)
    {
        String firstch;
        String restStr;

        // base case s length is 1 just return s
        if (s.length() == 1)
            return s;
        // recursive case
        firstch = s.substring(0, 1);  // get the first character
        restStr = s.substring(1);     // get the rest of the string

        // reverse the string by moving the first char to the end and the
        // reverse of the rest of the string on the front.
        return revStr(restStr) + firstch;   
    }

    public static void main(String[]args)
    {
        String teststr = "reverse this";
        NODString nod = new NODString();
        System.out.println("The reverse of "+teststr+" is "+nod.revStr(teststr));
    }

}

The output from the above program is:

run:
The reverse of reverse this is siht esrever
BUILD SUCCESSFUL (total time: 1 second)

References

1. Abelson, Harold, Gerald Jay. Sussman, and Julie Sussman. Structure and Interpretation of Computer Programs. Cambridge, MA: MIT, 1985. Print.
2. "Welcome to the SICP Web Site." Welcome to the SICP Web Site. N.p., n.d. Web. 01 Jan. 2013. http://mitpress.mit.edu/sicp/.
3. Sedgewick, Robert, and Kevin Wayne. "Introduction to Programming in Java." Introduction to Programming in Java. Addison-Wesley, n.d. Web. 01 Jan. 2013. http://introcs.cs.princeton.edu/java/home/.

Author: Nasty Old Dog