In this Fibonacci function which works, doesn't it pass the number of elements that can be stored in the array?

Question

This is my code and it works. For example, when n=5, it returns 5. Since n=5, and defining arr[0] = 0, isn't there only four more spaces left to store the elements from arr[1] to arr[4]? However, it seems like 6 elements(from arr[0] to arr[5]) could be stored and I do not know how.

int fibonacci(int n) {
    int i;
    int arr[n];
    arr[0] = 0;
    for(i=1; i<=n; i++)
    {
        if(i==1)
        {
        arr[i] = 1;
        }
        else
        {
        arr[i] = arr[i-2] + arr[i-1];
        }

    }
    return arr[n];   
}

[Why aren't variable-length arrays part of the C++ standard?](https://stackoverflow.com/questions/1887097/why-arent-variable-length-arrays-part-of-the-c-standard) — Evg, Dec 20 '19 at 10:21
Two problems: First C++ doesn't have [variable-length arrays](https://en.wikipedia.org/wiki/Variable-length_array); Use e.g. [`std::vector`](https://en.cppreference.com/w/cpp/container/vector) instead. Secondly the condition `i <= n` will make `i` go out of bounds of the array leading to *undefined behavior*. — Some programmer dude, Dec 20 '19 at 10:21
Yes, I thought i goes out of bounds but don't know why it still works. — user11591356, Dec 20 '19 at 10:26
Appearing to work despite being broken is one example of undefined behaviour. — molbdnilo, Dec 20 '19 at 10:28
Does this answer your question? [Accessing an array out of bounds gives no error, why?](https://stackoverflow.com/questions/1239938/accessing-an-array-out-of-bounds-gives-no-error-why) — Karsten Koop, Dec 20 '19 at 10:45

Frederik Juul · Answer 1 · 2019-12-20T11:58:16.410

This is undefined behaviour.

Behind the scenes

What's going on behind the scenes is that 5 ints are allocated on the stack. Lets say they're put at address 0x20 to 0x30. The array notation [] is really syntax sugar for using pointers. This means that arr[0] really is a pointer to 0x20. Your array in this case translates to the following addresses (because sizeof(int) = 4):

arr[0] = (arr+0) = 0x20

arr[1] = (arr+1) = 0x24

arr[2] = (arr+2) = 0x28

arr[3] = (arr+3) = 0x2C

arr[4] = (arr+4) = 0x30

This is all fine and good, you're operating on allocated memory. What happens when you try to write to index 5? Well, the same thing, basically:

arr[5]= (arr+5) = 0x34.

It's still just a pointer to an address that you want to write to. The problem is, however, that you haven't told anyone that you intend to write to that address - the memory has not been set aside for you.

If it has not been set aside for anything else, this will likely turn out alright - as you observe.

However if it has it can turn into all sorts of strange behavior depending on what it was used for. Maybe it has been set aside and is just not used yet, maybe it has been used but is simply overwritten and will not be checked again. The point is we don't know! Therefore it is dangerous and undefined.

The reason why it even works in the first place, is that - again - it is just dereferencing a pointer. And dereferencing a pointer should work, as you're trusted to know more that the compiler. It may warn you that you probably shouldn't do this, but it's not an error per se.

What you should do instead

When working with variable length arrays in C++, one should use the modern tools available since C++11. In this scenario, it's advisable to use std::vector instead. If you use the at function rather than [] it checks whether the index is inside the bounds.

Thank you for your comment! – user11591356 Dec 20 '19 at 23:54 — user11591356, Dec 20 '19 at 23:54

score 1 · Answer 2 · answered Dec 20 '19 at 12:22

Its unexpected behavior, even warn by C++ documents, maybe they removed out-boundary checking. Not only that, you even assign to it. So better to be under range.

#include <iostream>

using namespace std;

int main(){
    int i, n = 5;
    int arr[n];
    arr[0] = 0;
    arr[1] = 1;

    for(i=2; i<n; i++){
        arr[i] = arr[i-2] + arr[i-1];
    }
    arr[8]=99; //assigning out of range
    //accessing out of range
    for(i=0;i<20;i++){
        cout<<arr[i]<<" ";
    }   
}

#OUT: 0 1 1 2 3 0 211951624 1 99 32766 -484579280 32766 -1740650656 32767 -484579408 32766 5 0 5 0

score 0 · Answer 3 · answered Dec 20 '19 at 11:59

You are facing issues with the int array. int arr[n]; is not valid C++ code if n is not fix at compile time. You can rewrite your code with the help of std::vector as

int fibonacci(int n) {
    std::vector<int> arr(n);
    arr[0] = 0;
    for(int i=1; i<=n; i++)
    {
        if(i==1)
        {
        arr[i] = 1;
        }
        else
        {
        arr[i] = arr[i-2] + arr[i-1];
        }

    }
    return arr[n];   
}

Comments:

Your code will use a lot of memory for large Fibonacci numbers, since you store the entire series. This is superfluous, since only have to store the last two entries of the Fibonacci series.
You don't have to loop over n in order to calculate the Fibonacci number. The Moivre-Binet formula gives a much quicker way of calculating these.

score -1 · Answer 4 · answered Dec 20 '19 at 10:21

-1

 for(i=1; i<=n; i++)

the for loop wil run if i is less than or equal to n, which means that when n = 5, it will still run.

answered Dec 20 '19 at 10:21

Dennis

1
1

1

Yes, but isn't arr[5] supposed to be out of bound since arr[0] = 0 was defined above so the index can go up to 4? – user11591356 Dec 20 '19 at 10:24
1

@user11591356 that is correct, what you're seeing is UB, you might be lucky that there wasn't any other data stored right behind the array so you didn't get access violations or segfaults, but the code you posted definitely is not correct – Florian Humblot Dec 20 '19 at 10:45

In this Fibonacci function which works, doesn't it pass the number of elements that can be stored in the array?

4 Answers4

Behind the scenes

What you should do instead