Слишком хорошо тоже нехорошо: это gcc оптимизирует сразу до готового ответа. Чтобы содержательно хвостовая рекурсия соптимизировалась, но сами вычисления остались, нужно что-нибудь чуток посложнее. Как-то так:

#include <stdio.h>

int fill_stack(int n)
{
    int m = n;
    while (m) {
        m >>= 1;
        n ^= m;
    }
    --n;
    if (n <= 0) return 0;
    n = n ^ (n >> 1);
    return fill_stack(n);
}

int main()
{
    int n = 1000000000;
    n = n ^ (n >> 1);
    printf("%d\n", fill_stack(n));
}

На процессоре из 2010 года выполняется 25 секунд, но стек не переполняет. Можно ещё в ассемблерный текст заглянуть, там видно, как из этого получился цикл.