Why is my variable not increasing after each recursion?

Question

So I'm pretty new to C++ and I'm trying to generate Fibonacci numbers using recursion right? Except when I try to index to the next value I need to increase the index, and the function won't let me increase it.

How I know, is that I've run it in debug mode and stepped over the function - it continuously loops inside the fibGen function with i staying at a constant value of 1 (When I call fibGen in my main function the parameters are (startingSeq, 1, 13), where startingSeq is another vector with values {1,1}

The code builds and compiles fine, but when I run it I get a memory alloc error, which is obv caused by the infinite loop it seems to have.

What have I done wrong? Why doesn't the 'i' increase?

I've tried increasing i by having i++ inside the recursive fibGen call (in the else statement), I've tried having i++ outside the function call, and I've tried what's in there right now, where I have i+=1 and then pass i through.

Also I didn't have the 'return fibSeq' down the bottom originally because it doesn't make sense to have it there, but I put it in because vscode wouldn't compile without it in there, saying that it could never reach the end of fibGen (which makes sense now, and when this problem's fixed I think it can be removed, but at the moment it's just there so that the program will compile)

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

The output should be a vector containing the Fibonacci sequence, and I'm getting a mem alloc error (described above)

1. What does `fibGen` return? 2. **Where** does `fibGen` return this ? 3. Where in `fibGen` does `fibGen` *not* return *anything* ? You said *"I didn't have the 'return fibSeq' down the bottom originally because it doesn't make sense to have it there"*. if the function isn't supposed to return anything via `return`, then why is it defined to do so? (e.g why isn't it `void fibGen(...)` )? At least then it becomes clear your intent *may* be to pass `fibSeq` by reference or the function couldn't possibly work. — WhozCraig, Jun 04 '19 at 00:56
Consider using `fibGen(const std::vector& fibSeq, const int i, const int max)` as a signature, then call `fibGen(fibSeq, i + 1, max)`. Try and `const` as much as you reasonably can to allow for optimization and avoid accidental data mutation. — tadman, Jun 04 '19 at 00:58
What does the & do for the vector fibSeq in the parameters? It worked, like i created a new variable b=i and then incremented b when calling fibGen within the recursion and it outputs the fibonacci sequence now, but how come the & changes how it works? — wertie8297, Jun 04 '19 at 01:00
@wertie8297 Apparently you're class/tutorial hasn't talked about [references](https://en.wikipedia.org/wiki/Reference_(C%2B%2B)) yet. And note, this *can* be done without them, but rather inefficiently. — WhozCraig, Jun 04 '19 at 01:02
I'm self teaching at the moment - I'm first year and have looked at Python and C, but was really liking C so started to look at C++. Still very early on though, like I spent most of yesterday trying to get Vscode to work with SFML and gcc. I've been scouring for tutorials and whatnot but everything seems to either be "let's make Hello World" or "let's make Photoshop" and I'm stuck here like "well shit" - any tips/suggestions for learning these kind of things outside of class? At the moment I just decided to work through Project Euler, but not sure how much depth that's actually going to give — wertie8297, Jun 04 '19 at 01:11
@wertie8297 C++ is an amazing language, an can be *incredibly* dense and/or complex. C++11 was a milestone a *long* time coming, and we were all eternally grateful the day it was ratified. Since then, even more amazing things have come to pass. Spend a *lot* of time on [cppreference.com](https://en.cppreference.com/w/) reading articles and studying the standard library offerings. It's really the best reference site you'll find. And of course, read as much professionally written code as you can. — WhozCraig, Jun 04 '19 at 01:23
@WhozCraig This is great, thanks for the link! for professional code do you just browse through Github? In my Python class they spent a fair bit of time teaching us how to write clean code, but I feel like it was pretty specific to Python so I'm a bit worried about picking up bad habits with C++. Are there better places to be browsing actual code? I thought about looking at open source programs like Unreal Engine but at the same time those kind of projects are massively complex and probably out of my scope at this stage — wertie8297, Jun 04 '19 at 02:12

score 3 · Accepted Answer · answered Jun 04 '19 at 00:58

3

Actually, your code kind of works. You are just handling the vector of results sub-optimally. With your declaration:

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

you will always pass copies of the vector around (and you are never using the returned value). Instead, what you probably want to do is to work on the same data. To do this, use a reference to a vector (denoted by &). Then, you do not need to return anything:

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

answered Jun 04 '19 at 00:58

Nico Schertler

32,049
4
39
70

Thanks a heap! So how come the & works? It has something to do with pointers right? Like the & references the address of fibSeq so that whenever fibSeq has .push_back() performed it'll extend on the address passed to it in the parameters, which in this case is the vector fib right? – wertie8297 Jun 04 '19 at 01:05
Also (pressed enter, meant to make another paragraph), but what's that syntax for your for loop in main? At the moment I use the classic for loop from C with i=0;i<=asdlfk etc, but that looks more like a Python for loop than a C loop? Does it literally iterate over everything in the fib vector, determine what type it is and then set whatever value it's up to to be the variable i? – wertie8297 Jun 04 '19 at 01:06
@wertie8297 It's ranged-for, a feature added in C++11. Additional features can make the sequence even more compact, even without lvalue-references, using [move-semantics](https://stackoverflow.com/questions/3106110/what-is-move-semantics) and [NRVO](https://en.cppreference.com/w/cpp/language/copy_elision), for example. [See it live](https://ideone.com/82qp2u). – WhozCraig Jun 04 '19 at 01:20

score 0 · Answer 2 · answered Jun 04 '19 at 02:42

So, I could not reproduce the error, until I realized that in your actual code, you were doing this instead of the code you posted:

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

In Visual Studio 2010, at least, it compiled fine, but threw an error at runtime, which I believe is what you described. So I'm going to assume I reproduced it.

The reason this is throwing an error is because you are invoking C++'s infamous undefined behavior. Undefined behavior in C++ permits anything to happen, like not failing to compile, but throwing a runtime error.

The fix is simple, really. You just need to return a value in all execution paths. Or, simply put, just do this:

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

Of course, you can take Nico Schertler's suggestion instead too:

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

It should be noted that not returning a value from a void function is not undefined behavior (that I'm aware), but actually how void's intended to work, so this function is fine not returning a value.

Why is my variable not increasing after each recursion?

2 Answers2