Hmm, wouldn't it be better to prove that the optimizations on a loop can also be performed on a recursion and then applying it? If they can't do that, how can they take the optimized loop, turn it back into a recursive structure, and assume that it is functionally identical to the starting recursive loop?

▲

fluoridation 2 days ago | parent [-]

Presumably because each transformation step preserves semantics. What I'm wondering is what the point of the round-trip conversion is. If you've gone to the trouble of turning a function into an iteration, just leave like that.

▲

Spivak 2 days ago | parent | next [-]

My guess would be because the transformation would be a user-visible change. If they produce a stack trace inside it wouldn't look as they expect.

▲

ambicapter 2 days ago | parent | prev [-]

That's my question, if each transformation step preserves semantics, how come they can't apply the optimization on the recursive form? I'm asking seeking clarification.

	▲	fluoridation a day ago \| parent [-]
		In general, proving things about recursive functions is more difficult. I could be wrong, but I think for example control flow graph builders usually stop at function boundaries, to keep the problem tractable. Turning a recursive function into an iteration makes it so you can see the whole execution as a single call, instead of having to hop around a virtual call stack. What I'm wondering is how they're able to turn the optimized form back into a recursive function. Surely there must be some recursive functions that if you optimize them they turn into simple loops or even a linear function is they're very bad.