Focus with C++

Question

C++ / C#

#include <vector>
#include <iostream>

std::vector<int> v;

// Функция дописывает в вектор v
// суммы цифр ненулевых префиксов двоичного представления числа x,
// начиная с самого длинного префикса
// например для числа 5 = 0b101, в вектор будет записано {2, 1, 1}, префиксами будут: {101, 10, 1}
//
// Возвращает сумму цифр самого длинного префикса - то есть самого числа в двоичной записи. Для 5 вернёт 2.
int f(const int x)
{
        // рекурсивная реализация

        if(x != 0) {
                // временно дописываем в конец вектора x % 2 (последний бит числа)
                // чтобы зарезервировать место для ответа
                v.push_back(x % 2);

                // запоминаем элемент в векторе, который нужно будет позже вычислить
                const size_t i = v.size() - 1;

                // вызываем рекурсивно функцию для x / 2, она обработает все мЕньшие префиксы
                // и вернёт ответ для наибольшего из них
                // нам нужно лишь добавить этот ответ к v[i],
                // самый младший бит уже был push_back-нут несколькими строками ранее

                v[i] += f(x / 2);

                // возвращаем ответ
                return v[i];

        }
        else {
                // тривиальный случай
                return 0;
        }
}

int main()
{
        // запускаем функцию для проверки
        f(5);

        // выводим ответ
        for(size_t i = 0; i < v.size(); ++i) {
                std::cout << v[i] << ' ';
        }
        std::cout << std::endl;

        return 0;
}

Yet another test for knowledge of the language =)
What will the program display and why?

Answer 1

It looks like push_back reallocates memory, so the reference obtained from v[i] after returning from the recursion becomes invalid. It's easy to see if you compare &v[i] before and after the recursive call. If you reserve space in the array in advance, everything will work as it should. I wonder, though, why the program doesn't crash when it writes to the wrong memory. Well, you would expect a vector to reserve at least a dozen elements by default (some variants of string seem to do this).

Answer 2

Thank you for the task, I have long wanted to write about ways to debug such errors, and here you have thrown such a wonderful example. Wrote .