Разница между возвратом функции и вызовом функции в рекурсии - PullRequest
Новая
       7

Разница между возвратом функции и вызовом функции в рекурсии

2 голосов
/ 15 марта 2020

Вот простой код двоичного поиска в C ++: 

int binarySearch(vector<int> &vec, int start, int end, int element) {
    int middle = 0;
    if (start <= end) {
        middle = start + (end - start) / 2;
        if (vec[middle] == element) {
            return middle;
        }
        else if (vec[middle] < element) {
            binarySearch(vec, middle + 1, end, element);
        }
        else {
            binarySearch(vec, start, middle - 1, element);
        }
    }
    return -1;
}

Он всегда дает результат -1. Теперь я знаю, что на этапе разматывания стека функции вызывается последний возврат -1.

Однако следующий код работает просто отлично: 

int binarySearch(vector<int> &vec, int start, int end, int element) {
    int middle = 0;
    if (start <= end) {
        middle = start + (end - start) / 2;
        if (vec[middle] == element) {
            return middle;
        }
        else if (vec[middle] < element) {
            return binarySearch(vec, middle + 1, end, element);
        }
        else {
            return binarySearch(vec, start, middle - 1, element);
        }
    }
    return -1;
}

Я хочу знать, что именно чем разница между возвратом функции и вызовом функции?

...