;; ================ Tail recursion ==========================

;; Tail-recursive functions are those in which the recursive call 
;; is the last operation in the function, i.e. no work is done
;; after the recursive call

;; Usually such functions require extra "accumulator" parameter

;; The advantage of tail recursion is that the time overhead of 
;; a function call can be eliminated

;; Example: tail-recursive sum of list:

;; sum-tail: list number -> number
;; the function computes the sum of a list of numbers
;; the second parameter is used as an accumulator and
;; is 0 on the first call
(define (sum-tail lon current-sum)
  (cond
    [(empty? lon) current-sum]
    ;; a tail recursive call. The element is added to the accumulator
    [else (sum-tail (rest lon) (+ current-sum (first lon)))] 
  )
)


(check-expect (sum-tail (list 1 2 3 4) 0) 10)

;; filter-tail-even: lon lon -> lon
;; the function filters out all non-even numbers
(define (filter-tail-even lon accum-lon)
  (cond
   [(empty? lon) accum-lon]
   [(even? (first lon)) (filter-tail-even (rest lon)
                                         (append accum-lon (list (first lon))))]
   [else (filter-tail-even (rest lon) accum-lon)]
  )
)

(check-expect (filter-tail-even (list 1 2 3 4 5 6) empty) (list 2 4 6))

;; using local to hide extra parameters for tail-recursion

;; sum: list of numbers -> numbers
;; computes the sum of all numbers in a list
(define (sum lon)
 (local ((define (sum-tail1 lon current-sum)
         (cond
           [(empty? lon) current-sum]
           [else (sum-tail1 (rest lon) (+ current-sum (first lon)))] 
           ))
         )
  ;; hiding tail recursion, setting initial accumulator value
  (sum-tail1 lon 0))
)


(check-expect (sum (list 1 2 3 4)) 10)

;; define a tail-recursive map-square

;; square: number -> number
;; computes the square of a number
(define (square x) (* x x))


;;(check-expect (map-square-tail (list 1 2 3) empty) (list 1 4 9))



;; define a tail-recursive reverse-list

;;(check-expect (reverse-list-tail (list 1 2 3) empty) (list 3 2 1))


;; define a general tail-recursive map, filter, and foldr functions