将递归转换为迭代

Question

我正在尝试将这个递归方法转换为迭代方法，但是我有些困惑，因为我的书没有足够的解释。这个方法在两个值之间的数组中搜索一个特定的值，并返回其索引。如能提供任何帮助或指点方向都将不胜感激。

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

- Tommy

---

这是一道练习题吗？也许你应该再考虑一下，然后你就能想明白了。 - Adam Arold

你知道大多数人都试图做相反的事情。将迭代转换为递归。 - Roddy of the Frozen Peas

Answer 1

在这个例子中，实际上转换非常容易。基本上，你只需要在一个循环中包含整个函数，并修改参数，而不是进行递归调用。

在函数中存在多个递归调用的情况下（例如遍历树），它变得更加复杂；然而，在这种情况下，迭代版本和递归版本几乎相同。

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);
}

- Sam Dufel

Answer 2

当你有尾调用时，你可以这样做。请考虑以下内容。

int f(int x, int y) {
  if (x == 0) { return y; }
  return f(y - 1, x);
}

等同于

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
  }
}

当您的方法调用其他方法时，这两种写法在语义上并不完全相同，因为Java允许调用堆栈内省，但是由于调用堆栈与被调用者不同而导致问题的可能性很小--您最有可能遇到的问题是无限循环而不是StackOverflowError。

- Mike Samuel

Answer 3

您可以这样做。确定参数并将其转换为循环变量。不要调用函数，更新变量。不要从函数返回 - 从循环中退出：

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

- Will Ness

Answer 4

我可以假设，在此方法的第一次调用中，first=0且last=anArray.length。

从那里开始，我建议以下操作

public static int binarySearch_iterative(int[] anArray, int value) {
    int first, last, mid, index;
    first = 0;
    last = anArray.length - 1; // The last cell of the array

    while(first <= last) {
        mid = (first + last) / 2;
        if(anArray[mid] == value) {
            index = mid;
            break;
        } else {
            if(value < anArray[mid]) {
                last = mid;
            } else {
                first = mid;
            }
        }
        if(first > last) {
            index = -1;
            break;
        }
    }
    return index;
}

希望这能对你有所帮助。

- Barranka