[zucker42]

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.

[nv-vn]

I'd be very surprised if there's a commercial compiler that would automatically optimize this into linear time. Maybe some obscure functional research language? But certainly don't think LLVM is capable of dynamic programming.