[ianthehenry]

Are there any existing compilers that could compile a function like this -- non-tail recursive and non-tail recursive modulo cons -- into something that executes in sub-exponential time? How would that even work? I've never heard of a compiler sufficiently smart to optimize a definition like this and now I'm very curious

[Joker_vD]

Well, both Clang [0] and GCC [1] do compile the "insanely-recursive" fib into something less insane (or, in case of GCC, something that's insane in a different way). It looks like it's done with partial unrolling/inlining?

And, well, if you disregard heavy optimizations, then this "insanely-recursive" function is actually a somewhat decent way to measure the efficiency of the function calls and arithmetic.

[0] https://godbolt.org/z/3fce1qTdv

[1] https://godbolt.org/z/4jqa453qY