Tail recursive sum #
(define (sum xs)
(if (empty? xs)
0
(+ (first xs) (sum (rest xs)))))
This isn’t tail recursive however. The recursive call must be the last call in the function. Lets define it tail recursively, we can use an accumulator:
Invariant: acc + sum of xs is desired answer.
(define (sum-helper acc xs)
(if (empty? xs)
acc
(sum-helper (+ acc (first xs)) (rest xs))))
(define (sum xs)
(sum-helper 0 xs))
(sum '(1 2 3 4)) ; 10