[fdej]

gcc already optimises away loops like for (i = 0; i < n; i++) s += i;

It wouldn't be too much of a stretch to detect and optimise away code that computes linearly recurrent sequences.

[mbel]

gcc removes recursion in that case: https://godbolt.org/g/R6iBup