将递归转换为迭代

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

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