Q:

Convert Recursion to Iteration

I'm trying to convert this recursive method to an iterative and I'm a bit stuck as my book doesn't explain it enough. This method searches an array between two values for a specific value and returns the index. Any help or a point in the right direction would be appreciated.
public static int binarySearch(int anArray[], int first, int last, int value) {
    int index;

    if (first > last) {
        index = -1;
    } else {
        int mid = (first + last) / 2;

        if(value == anArray[mid]) {
            index = mid;
        } else if(value < anArray[mid]) { //Point x
            index = binarySearch(anArray, first, mid - 1, value);
        } else { //Point Y
            index = binarySearch(anArray, mid + 1, last, value);
        }
    }

    return index;
}

A:

In this is instance, it's actually a pretty easy conversion.  Basically, you just wrap your entire thing in a loop, and modify your parameters rather than making recursive calls.
In situations where you have multiple recursive calls in a function (such as traversing a tree), it becomes much more complicated; however, in this case the iterative version and the recursive version are almost identical.
public static int binarySearch(int anArray[], int first, int last, int value) {

    do {
        if (first > last) {
            return -1;
        } else {
            int mid = (first + last) / 2;

            if(value == anArray[mid]) {
                return mid;
            } else if(value < anArray[mid]) { //Point x
                last = mid - 1;
                //index = binarySearch(anArray, first, mid - 1, value);
            } else { //Point Y
                first = mid + 1;
                //index = binarySearch(anArray, mid + 1, last, value);
            }
        }
    }
    while(true);
}

A:

This can be done when you've got tail calls.  Consider that
int f(int x, int y) {
  if (x == 0) { return y; }
  return f(y - 1, x);
}

is equivalent to
int f(int x, int y) {
  while (true) {
    // The body of your method goes here as normal.
    if (x == 0) { return y; }
    // Instead of returning the result of a recursive call though,
    // compute the parameters to tail call
    int newX = y - 1;
    int newY = x;
    // overwrite parameters with values to tail call
    x = newX;
    y = newY;
    // let the loop jump us back to the top of the method.
    continue;  // You can put continue in place of return
  }
}

These aren't quite semantically equivalent when your method calls other methods because Java allows Call stack introspection but you're unlikely to run into problems as a result of the call stack being different to a callee -- the most likely problem you'll run into is you'll get an infinite loop instead of a StackOverflowError.

A:

You do it like this. Identify the arguments and make them into loop variables. Instead of calling the function, update the variables. Instead of returning from function - exit from the loop:
public static int binarySearch(int anArray[], int first, int last, int value) {
  int index;
  int done = 0;              // LOOP CONTROL

  while (done == 0) {        // A LOOP:

    if (first > last) {
        index = -1;          // RETURN ---> EXIT FROM LOOP
        done = 1;
    } else {
        int mid = (first + last) / 2;

        if(value == anArray[mid]) {
            index = mid;     // RETURN ---> EXIT FROM LOOP
            done = 1;
        } else if(value < anArray[mid]) { //Point x
            // index = binarySearch(anArray, first, mid - 1, value);
            // CALL ---> UPDATE THE VARIABLES
            last = mid-1;
        } else { //Point Y
            // index = binarySearch(anArray, mid + 1, last, value);
            // CALL ---> UPDATE THE VARIABLES
            first = mid+1;
        }
    }
  } // END LOOP

  return index;
}

