;=======================================================================================
; lecture trace 3 part 2 -- tail recursion & recur
;=======================================================================================

; tail recursion without recur - a useful technique but
; can often be made more efficient

;=================================
; factorial
;=================================

(defn tfact1
  ([n]   (tfact1 n 1))
  ([n r] (if (zero? n) r
           (tfact1 (dec n) (* r n)))
      ))


user=> (tfact1 5)
120
user=> (tfact1 1)
1
user=> (tfact1 0)
1


;=================================
; sum of numbers up to some n
;=================================

(defn sum-upto
  ([n]    (sum-upto n 0))
  ([n r]  (if (zero? n) r
            (sum-upto (dec n) (+ n r)))
    ))


user=> (sum-upto 9)
45
user=> (sum-upto 5)
15



;=================================
; find the length of a list
;=================================

(defn length
  ([lis]   (length lis 0))
  ([lis n] (if-not (seq lis) n
             (length (rest lis) (inc n)))
    ))


user=> (length '(a b c d))
4
user=> (length ())
0
user=> (length nil)
0



;=================================
; sum a list of numbers
;=================================


(defn sum-list
  ([lis]    (sum-list lis 0))
  ([lis n]  (if-not (seq lis) n
              (sum-list (rest lis) (+ (first lis) n)))
    ))

user=> (sum-list '(5 2 4 3 1))
15



; now we do tail recursion with recur - more efficient
;--------------------------------------------------------------------------------------


;=================================
; factorial with recur
;=================================
; NB: you can only recur within the same variadic form
; - you cannot recur from one variadic form to a different one


(defn tfact
  ([n]   (tfact n 1))
  ([n r] (if (zero? n) r
           (recur (dec n) (* n r)))
    ))


user=> (tfact 5)
120
user=> (tfact 1)
1
user=> (tfact 0)
1



;=================================
; sum of numbers with recur
;=================================

(defn sum-upto
  ([n]   (sum-upto n 0))
  ([n r] (if (zero? n) r
           (recur (dec n) (+ n r)))
    ))


user=> (sum-upto 9)
45
user=> (sum-upto 5)
15


;=================================
; factorial with recur & loop
;=================================
; loop is used when it is convenient to have a recursion
; point somewhere within a fn body (so these examples
; are a little unrealistic)

(defn tfact [n]
  (loop [n n
         r 1
         ]
    (if (zero? n)
      r
      (recur (dec n) (* n r)))
      ))


user=> (tfact 5)
120
user=> (tfact 1)
1
user=> (tfact 0)
1



;=================================
; sum numbers with recur & loop
;=================================

(defn sum-upto [n]
  (loop [n n
         r 0
         ]
    (if (zero? n) r
      (recur (dec n) (+ n r)))
    ))


user=> (sum-upto 9)
45
user=> (sum-upto 5)
15


; recur versions of length and sum-list will be tutorial exercises