Is a recursive function in Scheme always tail-call optimized? -
i've read tail-call optimization in scheme. i'm not sure whether understand concept of tail calls. if have code this:
(define (fac n) (if (= n 0) 1 (* n (fac (- n 1)))))
can optimized, won't take stack memory? or can tail-call optimization applied function this:
(define (factorial n) (let fact ([i n] [acc 1]) (if (zero? i) acc (fact (- 1) (* acc i)))))
a useful way think tail calls ask "what must happen result of recursive procedure call?"
the first function cannot tail-optimised, because result of internal call fac
must used, , multiplied n
produce result of overall call fac
.
in second case, however, result of 'outer' call fact
is... result of inner call fact
. nothing else has done it, , latter value can passed directly value of function. means no other function context has retained, can discarded.
the r5rs standard defines 'tail call' using notion of tail context, i've described above.
Comments
Post a Comment