Menu
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)))))
942
There are many problems where you are trying to do optimization. That is, you are attempting to find a way of doing something that maximizes or minimizes some quantity. A recursive divide and conquer approach is often successful for dealing with such problems.
As always, it depends As a rule of thumb; tail-recursive functions are faster if they don't need to reverse the result before returning it. That's because that requires another iteration over the whole list. Tail-recursive functions are usually faster at reducing lists, like our first example.
Scheme is “properly tail recursive”, meaning that tail calls or recursions from certain contexts do not consume stack space or other resources and can therefore be used on arbitrarily large data or for an arbitrarily long calculation.
The tail recursion is better than non-tail recursion. As there is no task left after the recursive call, it will be easier for the compiler to optimize the code. When one function is called, its address is stored inside the stack. So if it is tail recursion, then storing addresses into stack is not needed.
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.
173
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.
35
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
