Question

I'm familiar with the idea of basic tail recursion elimination, where functions that return the direct result of a call to themselves can be rewritten as iterative loops.

foo(...):
    # ...
    return foo(...)

I also understand that, as a special case, the function can still be rewritten if the recursive call is wrapped in a call to cons.

foo(...):
    # ...
    return (..., foo(...))

What property of cons allows this? What functions other than cons can wrap a recursive tail call without destroying our ability to rewrite it iteratively?

GCC (but not Clang) is able to optimize this example of "tail recursion modulo multiplication," but it's unclear what mechanism allows it to discover this or how it makes its transformations.

pow(x, n):
    if n == 0: return 1
    else if n == 1: return x
    else: return x * pow(x, n-1)

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top