遞迴

一般遞迴

遞迴是函式透過不斷呼叫自己，將問題切割成數個細小問題逐個解決之後，把結果統整起來的問題解決方式。函數式程式設計語言透過遞迴達成迴圈可以做到的事。

如果想要用遞迴來解決問題，首先必須要先將問題切割成有限的小問題，再來則要確定解決最小問題的方法。只要完成這兩件事，問題便可以順利解決。

舉例來說階乘函數的定義是：n! = n * (n - 1) * (n - 2) · · · 3 * 2 * 1，可以把 n 的階乘看成 n 乘上 (n - 1) 的階乘，而 (n - 1) 的階乘則是 (n - 1) 乘上 (n - 2) 的階乘。因此計算階乘只要不斷計算下一個階乘的值，直到 1 爲止將它們全部相乘：

(defn factorial [n]
  (if (= n 1)
    1
    (*' n (factorial (- n 1)))))
(factorial 10)
;; => 3628800

以上的範例中使用了會自動轉換成大數的乘法符號 *'，因爲產生的結果可能會超過一般整數的大小。

雖然這樣的表現非常自然直覺，但是缺點是因爲不斷呼叫自己，每次呼叫函式時會配置記憶體，其中存放參數資訊與到時返回的資訊，在最後一個函式返回之前，記憶體都不會釋放收回。一旦遞迴的次數過多，就會用光記憶體而無法正常運行：

(factorial 10000)
;; => StackOverflowError

尾遞迴

因此爲了解決一般遞迴會發生的記憶體不足的問題，可以使用尾遞迴 (Tail Recursion) 的方式解決。尾遞迴仍然是遞迴，但是將遞迴呼叫的位置擺放在函式的尾端，並且在遞迴呼叫函式之前，已完成呼叫之前必要的計算。以下是改成尾遞迴的範例：

(defn tail-factorial
  ([n]
   (tail-factorial 1 1 n))
  ([product counter max-count]
   (if (> counter max-count)
     product
     (tail-factorial (*' counter product)
                     (+ counter 1)
                     max-count))))
(tail-factorial 10000)
;; => StackOverflowError

在一些程式語言例如 Scheme 會將尾遞迴的函式進行效能改進，但是在 Clojure 寄宿的 JVM 中並不會對尾遞迴實行改進，因此建議的做法是改用 Clojure 提供的 loop/recur：

(defn recur-factorial [n]
  (loop [product 1
         counter 1
         max-count n]
    (if (> counter max-count)
      product
      (recur (*' counter product)
             (+ counter 1)
             max-count))))
(recur-factorial 10000)
;; => 28462596809170545189….0000N

惰性序列

將運算或求值延遲到必要的時候才進行稱作惰性求值 (Lazy evaluation)，Clojure 提供了惰性序列 (Lazy sequence) 將計算序列內容延遲到真正需要的時候。Lisp 家族中的 Scheme 程式語言提供了類似的功能稱爲流 (Stream)，Haskell 程式語言則是全面支援惰性求值。

因爲惰性序列延遲計算的特色，可以用來表現無限的概念，例如無限列表、或是讀取非常龐大的資料，在必要的時候才讀取資料至記憶體、或是將 IO 讀取延遲到真正需要的時候。內部使用的型態爲 clojure.lang.LazySeq。

(class (take 10 (range)))
;; => clojure.lang.LazySeq

創建一個惰性序列最簡單的方式是呼叫 range 函式，它會根據傳遞的參數創建漸進的惰性序列，搭配 take 函式後，可以依據需要的個數取得序列的內容：

(range 10)
;; => (0 1 2 3 4 5 6 7 8 9)
(range 1 11)
;; => (1 2 3 4 5 6 7 8 9 10)
(range 1 11 2)
;; => (1 3 5 7 9)
(take 5 (range))
;; => (0 1 2 3 4)

請記得千萬不要在 REPL 中直接使用 range 函式，會迫使 REPL 一直爲了顯示序列的內容而不斷求值，造成 REPL 停滯不動：

;; 危險！不要這樣做！！
(range)

repeat 創建惰性序列，內容為不斷重複的參數：

(take 3 (repeat "Hello"))
;; => ("Hello" "Hello" "Hello")

iterate 函式接受兩個參數，第一個參數爲一個函式，這個函式將會不斷地被運算，求值後的結果成爲惰性序列的內容；第二個參數則爲初始值：

(take 5 (iterate #(+ % 0.5) 1))
;; => (1 1.5 2.0 2.5 3.0)

以上範例中，iterate 第一個參數使用到了匿名函式 (Anonymous Function)。

cycle 函式接受一個群集，群集的內容將會交錯反覆地作爲惰性序列的元素：

(take 3 (cycle ["ping" "pong"]))
;; => ("ping" "pong" "ping")
(take 5 (cycle ["ping" "pong"]))
;; => ("ping" "pong" "ping" "pong" "ping")

map 與 filter 函式可以應用在惰性序列上，產生的結果也是惰性序列。以下範例示範了利用 filter 與 take 取得 0 到 100 中頭十個偶數：

(take 10 (filter even? (range 0 100)))
;; => (0 2 4 6 8 10 12 14 16 18)

當利用內建的函式產生的惰性序列不符合需求時，還可以利用 lazy-seq 依據自己的需求打造惰性序列。以下利用 lazy-seq 與遞迴，建立惰性的費式序列：

(defn fib-seq
  "Returns a lazy sequence of Fibonacci numbers"
  ([]
     (fib-seq 0 1))
  ([a b]
     (lazy-seq
        (cons b (fib-seq b (+ a b))))))
(take 10 (fib-seq))
;; => (1 1 2 3 5 8 13 21 34 55)

以上範例首先使用 lazy-seq 創建惰性序列，其中使用 cons 函式創建序列，序列的尾部遞迴地呼叫 fib-seq 繼續生成序列。

回顧

通過本篇文章，你知道了如何建立 Vars 物件儲存資料，也了解如何建立函式。還了解了函式的各方面特色，如多載以及不定引數等。知道了使用解構手法，可以更方便快速取得需要的資料；當然還有像堆積木一樣地任意組合函式。除此之外，還知道了遞迴以及可以表達無限概念的惰性序列。

還不賴吧？今天就先到這裡，下一篇文章再見囉！

（本篇文章同步刊登於 GitHub，歡迎在文章下方留言或發送 PR 給予建議與指教）