Почему моя переменная не увеличивается после каждой рекурсии? - PullRequest
Новая
       11

Почему моя переменная не увеличивается после каждой рекурсии?

1 голос
/ 04 июня 2019

Итак, я довольно новичок в C ++ и пытаюсь сгенерировать числа Фибоначчи, используя рекурсию, верно? За исключением случаев, когда я пытаюсь индексировать до следующего значения, мне нужно увеличить индекс, и функция не позволит мне его увеличить.

Насколько я знаю, я запустил его в режиме отладки и перешагнул через функцию - она ​​постоянно зацикливается внутри функции fibGen, и у меня остается постоянное значение 1 (когда я вызываю fibGen в моей основной функции, параметры являются (начальныйSeq, 1, 13), где начальныйSeq является другим вектором со значениями {1,1}

Код прекрасно собирается и компилируется, но когда я его запускаю, я получаю ошибку выделения памяти, которая вызвана бесконечным циклом.

Что я сделал не так? Почему «я» не увеличивается?

Я пытался увеличить i, имея i ++ внутри рекурсивного вызова fibGen (в операторе else), я пытался использовать i ++ вне вызова функции, и я попробовал то, что сейчас там, где у меня есть i + = 1, а затем пропустите i.

Также у меня изначально не было «return fibSeq» внизу, потому что его не имеет смысла, но я вставил его, потому что vscode не будет компилироваться без него, говоря, что это может никогда не доходить до конца fibGen (что имеет смысл сейчас, и когда эта проблема будет исправлена, я думаю, что ее можно удалить, но на данный момент она просто существует, так что программа будет компилироваться) 

std::vector<int> fibGen(std::vector<int> fibSeq, int i, int max){

    if(fibSeq[i] >= max){
        return fibSeq;
    }else{
        fibSeq.push_back(fibSeq[i] + fibSeq[i-1]);
        i+=1;
        fibGen(fibSeq, i, max);
    } 

    return fibSeq;  
}

На выходе должен быть вектор, содержащий последовательность Фибоначчи, и я получаю ошибку mem alloc (описанную выше)

Ответы [ 2 ]

3 голосов
/ 04 июня 2019

На самом деле, ваш код работает. Вы просто обрабатываете вектор результатов неоптимально. С вашей декларацией: 

std::vector<int> fibGen(std::vector<int> fibSeq, int i, int max)

вы всегда будете передавать копии вектора (и вы никогда не будете использовать возвращаемое значение). Вместо этого то, что вы, вероятно, хотите сделать, это работать с теми же данными. Для этого используйте ссылку на вектор (обозначается &). Тогда вам не нужно ничего возвращать: 

void fibGen(std::vector<int>& fibSeq, int i, int max) {

    if (fibSeq[i] >= max) {
        return;
    }
    else {
        fibSeq.push_back(fibSeq[i] + fibSeq[i - 1]);
        i += 1;
        fibGen(fibSeq, i, max);
    }
}

void main(void) {
    std::vector<int> fib = { 1, 1 };
    fibGen(fib, 1, 34);
    for (auto i : fib)
        std::cout << i << std::endl;
}
0 голосов
/ 04 июня 2019

Итак, я не мог воспроизвести ошибку, пока не осознал, что в вашем реальном коде вы делали это вместо того, что вы разместили: 

std::vector<int> fibGen(std::vector<int> fibSeq, int i, int max){

    if(fibSeq[i] >= max){
        return fibSeq;
    }else{
        fibSeq.push_back(fibSeq[i] + fibSeq[i-1]);
        i+=1;
        fibGen(fibSeq, i, max);
    } 
}

В Visual Studio 2010, по крайней мере, этоскомпилировано нормально, но выдает ошибку во время выполнения, что я считаю, что вы описали.Поэтому я предполагаю, что воспроизвел его.

Причина, по которой это выдает ошибку, заключается в том, что вы вызываете печально известное неопределенное поведение C ++ .Неопределенное поведение в C ++ допускает что-либо, что происходит , например, не компилирование, а генерирование ошибки времени выполнения.

Исправление действительно простое.Вам просто нужно вернуть значение во всех путях выполнения.Или, проще говоря, просто сделайте следующее: 

std::vector<int> fibGen(std::vector<int> fibSeq, int i, int max){

    if(fibSeq[i] >= max){
        return fibSeq;
    }else{
        fibSeq.push_back(fibSeq[i] + fibSeq[i-1]);
        i+=1;
        return fibGen(fibSeq, i, max); 
        // Notice we are returning the value of the recursive call to fibGen().
        // We can do this because we have already modified the vector the way we need to,
        // so just simply returning the value is fine
    } 
}

Конечно, вместо этого вы можете принять предложение Нико Шертлера : 

void fibGen(std::vector<int>& fibSeq, int i, int max) {

   if (fibSeq[i] >= max) {
       return;
   }
   else {
       fibSeq.push_back(fibSeq[i] + fibSeq[i - 1]);
       i += 1;
       fibGen(fibSeq, i, max);
   }
}

Следует отметить, что не возвращать значение из функции void - это не неопределенное поведение (насколько я знаю), а фактически то, как void должен работать, так что эта функция нормально не возвращает значение.

...