Рекурсивный Fibonacci

Причина в том, что последовательность Фибоначчи начинается с двух известных сущностей, 0 и 1. Ваш код проверяет только одну из них (являющуюся одной).

Измените свой код на

int fib(int x) {
    if (x == 0)
        return 0;

    if (x == 1)
        return 1;

    return fib(x-1)+fib(x-2);
}

, чтобы включить как 0, так и 1.

Почему бы не использовать итерационный алгоритм?

int fib(int n)
{
    int a = 1, b = 1;
    for (int i = 3; i <= n; i++) {
        int c = a + b;
        a = b;
        b = c;
    }           
    return b;
}