Is a recursive function in Scheme always tail-call optimized?

Question

I've read something about tail-call optimization in Scheme. But I'm not sure whether I understand the concept of tail calls. If I have code like this:

(define (fac n)
  (if (= n 0)
      1
      (* n (fac (- n 1)))))

can this be optimized, so that it won't take stack memory? or can tail-call optimization only be applied to a function like this:

(define (factorial n)
    (let fact ([i n] [acc 1])
      (if (zero? i)
          acc
          (fact (- i 1) (* acc i)))))

Answer 1

A useful way to think about tail calls is to ask "what must happen to the result of the recursive procedure call?"

The first function cannot be tail-optimised, because the result of the internal call to fac must be used, and multiplied by n to produce the result of the overall call to fac.

In the second case, however, the result of the 'outer' call to fact is... the result of the inner call to fact. Nothing else has to be done to it, and the latter value can simply be passed back directly as the value of the function. That means that no other function context has to be retained, so it can simply be discarded.

The R5RS standard defines 'tail call' by using the notion of a tail context, which is essentially what I've described above.

Answer 2

No, the first fac cannot be optimized.

When a function is called, you need to know the place it was called from, so that you can return to that location once the call is complete and use the result of the call in future computations (a fac function).

fact is implemented differently. The last thing that fact does is to call itself. There is no need to remember the place we are calling from — instead, we can perform tail call elimination. There is no other actions which should be done after the fact returns.