clojure thinking recursively | 递归 clj

00 [clojure的递归应用举例].md

clojure thinking recursively

char-counter.clj

(defn char-counter [str]
  (loop [counts {}
         s str]
    (if-not (empty? s)
      (let [c (first s)]
        (recur (assoc counts c (inc (get counts c 0)))
               (rest s)))
      counts)))

(char-counter "hello world")

convert-metric.clj

;; from the joy of clojure 

(def simple-metric {:meter 1,
                    :km 1000,
                    :cm 1/100,
                    :mm [1/10 :cm]})

;; How many meters
;; are in 3 kilometers, 10 meters, 80 centimeters, 10 millimeters?” you could use the map
;; as follows:

(-> (* 3 (:km simple-metric))
    (+ (* 10 (:meter simple-metric)))
    (+ (* 80 (:cm simple-metric)))
    (+ (* (:cm simple-metric)
          (* 10 (first (:mm simple-metric)))))
    float)
;;=> 3010.81

;; Although the map is certainly usable this way, the user experience of traversing
;; simple-metric directly is less than stellar. Instead, it would be nicer to define a function
;; named convert, shown in the following listing

(defn convert [context descriptor]
  (reduce (fn [result [mag unit]]
            (+ result
               (let [val (get context unit)]
                 (if (vector? val)
                   (* mag (convert context val))
                   (* mag val)))))
          0
          (partition 2 descriptor)))

(convert simple-metric [50:mm])

factorial.clj

;; from clojure koans 
;; https://www.youtube.com/watch?v=CLhjo_nG2AU

(defn factorial [n]
  (loop [n   n
         acc 1]
    (if (= n 0)
      acc 
      (recur (dec n) (* n acc)))))

(factorial 3) ;; 6

(factorial 4) ;;24
(factorial 5)

;; https://gist.github.com/5a43353e59b0dbc41cc3 

finite-state-machine.clj

(defn elevator [commands]
  (letfn
      [(ff-open [[_ & r]]
         "When the elevator is open on the 1st floor
it can either close or be done."
         #(case _
            :close (ff-closed r)
            :done true
            false))
       (ff-closed [[_ & r]
                   "When the elevator is closed on the 1st floor
it can either open or go up."
                   #(case _
                      :open (ff-open r)
                      :up (sf-closed r)
                      false))
         (sf-closed [[_ & r]]
                    "When the elevator is closed on the 2nd floor
it can either go down or open."
                    #(case _
                       :down (ff-closed r)
                       :open (sf-open r)
                       false))
         (sf-open [[_ & r]]
                  "When the elevator is open on the 2nd floor
it can either close or be done"
                  #(case _
                     :close (sf-closed r)
                     :done true
                     false))]
      
(trampoline ff-open commands)))

(elevator [:close :open :close :up :open :open :done])
                                        ;=> false
(elevator [:close :up :open :close :down :open :done])
                                        ;=> true
;; run at your own risk!
(elevator (cycle [:close :open]))                                       
 ; ... runs forever

recursive.clj

;; come from `the joy of clojure`

;; Mundane recursion
(defn pow [base exp]
  (if (zero? exp)
    1
      (* base (pow base (dec exp)))))

(pow 2 10)
;=> 1024
(pow 1.01 925)
;=> 9937.353723241924

(pow 2 10000)
; java.lang.StackOverflowError

;; recursive call
;; to occur in the tail position
;; This new version of pow uses two common techniques for converting mundane recursion
;; to tail recursion. First, it uses a helper function kapow that does the majority of
;; the work. Second, kapow uses an accumulator acc that holds the result of the multiplication.
(defn pow [base exp]
  (letfn [(kapow [base exp acc]
            (if (zero? exp)
              acc
              (recur base (dec exp) (* base acc))))]
    (kapow base exp 1)))
(pow 2N 10000)
;=> ... A very big number

sums.clj

;; A loop that sums the numbers 10 + 9 + 8 + ...
(defn sums [n]
  (loop [sum 0 cnt n]
    (if (= cnt 0)
      sum
      (recur (+ cnt sum) (dec cnt)))))

(sums 10)
;=> 55