iT邦幫忙

2018 iT 邦幫忙鐵人賽
DAY 10
0
Software Development

擁抱 Clojure系列 第 10

[第 10 天] 擁抱 Clojure:繫結與函式(四)

遞迴

一般遞迴

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

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

舉例來說階乘函數的定義是: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")

mapfilter 函式可以應用在惰性序列上,產生的結果也是惰性序列。以下範例示範了利用 filtertake 取得 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 給予建議與指教)


上一篇
[第 09 天] 擁抱 Clojure:繫結與函式(三)
下一篇
[第 11 天] 擁抱 Clojure:流程控制(一)
系列文
擁抱 Clojure30

尚未有邦友留言

立即登入留言