;; The first three lines of this file were inserted by DrScheme. They record metadata
;; about the language level of this file in a form that our tools can easily process.
#reader(lib "htdp-intermediate-lambda-reader.ss" "lang")((modname tail_recursion) (read-case-sensitive #t) (teachpacks ((lib "master.ss" "teachpack" "htdp") (lib "draw.ss" "teachpack" "htdp") (lib "gui.ss" "teachpack" "htdp"))) (htdp-settings #(#t constructor repeating-decimal #f #t none #f ((lib "master.ss" "teachpack" "htdp") (lib "draw.ss" "teachpack" "htdp") (lib "gui.ss" "teachpack" "htdp")))))
;; ================ 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)))] 
  )
)

(define (square x) (* x x))


(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
(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
(define (map-square-tail lon current)
  (cond
    [(empty? lon) current]
    [else (map-square-tail (rest lon) (append current (list (expt (first lon) 2))))]
)
  )

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



;; define a tail-recursive reverse-list
(define (reverse-list-tail lon current)
  (cond [(empty? lon) current]
        [else (reverse-list-tail (rest lon) (cons (first lon)current))]))
(check-expect (reverse-list-tail (list 1 2 3) empty) (list 3 2 1))