I had the (mistaken) impression that the GCC code signicantly transformed the algorithm because there is only one recursive call instruction, but looking at it closer it's still exponential. I still think it's a pretty silly idea to use such an unrealistic benchmark. Especially since it might be possible to make a compiler turn the exponential algorithm linear.