Recursion

在clojure中,主要靠递归来实现循环控制结构。记得在《c和指针》关于递归和迭代还有过详细介绍,有一些将二者互换的练习,如何形象地理解二者可以看这里。从时间复杂度上来说,二者是等价的。通常将循环结构改写成递归结构的伪代码可以这么写:

for(init, end-condition, change-state)
    do-something-here
    
f(state, & args)
    condition-meet?
        yes-do-something-and-return
        no-please-recur(state-update, do-something-with-args-and-return-updated-args)

当然,递归调用可以发生在函数体内的任何地方,不过,有一类特殊的递归发生在函数返回的地方,称为尾递归(Tail Call)。正是因为发生在函数返回的地方,函数体内的运行时信息不再需要保存,因而可以做到尾递归优化(TCO)。不过,受限于JVM,clojure的实现里,并不能直接做到TCO,举例如下:

(defn f [n] 
  (if (> n 0)
    (f (dec n))
    0))

(f 100)     ; 0
(f 100000)  ; StackOverflowError   clojure.lang.Numbers$LongOps.combine (Numbers.java:419)

不过在clojure中,提供了一种类似goto的语法,即loop和recur来实现从函数尾部跳转。如果函数体内没有显式地提供loop语句,则会跳转到函数开始处。这里loop在语义上和let语句是等价的,只不过添加了一个标记方便编译器识别。使用recur需要注意的是只能写在函数的返回处,不能像普通的递归一样对递归调用的结果做二次处理。

(defn factorial [x]
  (if (= 1 x)
   1
   (* x (factorial (dec x)))))
;; it's ok, but...
(factorial 10000N)  ;; CompilerException java.lang.StackOverflowError

(defn factorial-recur1 [x]
  (if (= 1 x)
    1
    (* x (recur (dec x)))))
;; this version will not pass compile
;; CompilerException java.lang.UnsupportedOperationException: Can only recur from tail position

(defn factorial-recur2 [x]
  (loop [n x
         acc 1]
    (if (= 1 n)
      acc
      (recur (dec n) (* n acc)))))

接下来考虑另一种情况,mutual recursion。假设定义了如下两个函数my-even?my-odd?

(declare my-odd? my-even?)    ;; make forward declarations first
(defn my-odd? [n]
      (if (= n 0)
          false
         (my-even? (dec n))))
(defn my-even? [n]
      (if (= n 0)
          true
         (my-odd? (dec n))))
         
(my-even? 10000)  ;; CompilerException java.lang.StackOverflowError

这里,由于在函数的结尾处是相互递归调用,需要保存堆栈信息,因此会造成StackOverflow,前面我们借用了looprecur实现了优化,那么这里能否用同样的套路呢?结果是不能!因为这样做相当于从一个函数内部goto到了另一个函数内部,recur显然是不会支持这样的操作的。为了解决这个问题,clojure中提供了一个有趣的函数trampoline

(defn trampoline
  ([f]
     (let [ret (f)]
       (if (fn? ret)
         (recur ret)
         ret)))
  ([f & args]
     (trampoline #(apply f args))))

其思想就是,每次执行完函数后,判断返回值是否仍然是函数,如果是,则recur然后继续执行,否则返回该值。然后,我们可以将my-odd?my-even?最后的函数互调用封装在一个\(\lambda\)函数里,由trampoline去执行。由于返回值是一个\(\lambda\)函数,相当于立即返回了,因而不会再有StackOverflowError的问题。

(declare my-even-helper? my-odd-helper?)  ;; make forward declarations first

(defn my-even-helper? [n]
  (if (zero? n)
    true
    #(my-odd-helper? (dec n))))

(defn my-odd-helper? [n]
  (if (zero? n)
    false
    #(my-even-helper? (dec n))))

(def my-even-new? (partial trampoline my-even-helper?))
(def my-odd-new? (partial trampoline my-odd-helper?))

除了用来解决mutual recursion的问题之外,trampoline还可以很优雅地用于解决有限状态机的问题,具体可以参考一些这里的例子.

Memoize

前面只是对recursion做了个简单的回顾,接下来聊一个自己写代码过程中实际遇到的问题。

问题是这样子的,Collatz Conjecture的简单描述如下:

给定任意一个正整数:1) 如果这个数是偶数,则对它除以2;2) 如果这个数是奇数,则对它乘以3以后加1。如此循环下去,最后都能够得到1。

找到1000000以内的某个数使得其收敛到1的步骤最长。

这里先不做过多的数学分析,先看一个最naive的版本:

(defn collatz-cnt [x]
  (loop [x x c 1]
    (if (= 1 x)
      c
      (recur (if (even? x) 
               (/ x 2)
               (inc (* 3 x)))
             (inc c)))))
             
(time (reduce #(let [c (collatz-cnt %2)]
                 (if (> c (first %1))
                   [c %2]
                   %1))
              [0 0]
              (range 1 1000000 2)))
;"Elapsed time: 8867.352869 msecs"
;[525 837799]

这么做显然很耗时,通过简单分析可以看出,遍历求collatz-cnt的过程中,会有大量的重复计算。如果能把中间结果缓存起来,那么应该能减少很多计算量。clojure中提供了一个memoize函数专门用来缓存函数调用的中间结果,与Python3中functools.lru_cache有点类似(不过没有lru)。其实现如下:

(defn memoize
  [f]
  (let [mem (atom {})]
    (fn [& args]
      (if-let [e (find @mem args)]
        (val e)
        (let [ret (apply f args)]
          (swap! mem assoc args ret)
          ret)))))

内部实际上就是通过(atom {})来实现缓存的,于是,我先简单地写了个缓存的版本:

(def collatz-cnt-memo (memoize collatz-cnt))

(time (reduce #(let [c (collatz-cnt-memo %2)]
                 (if (> c (first %1))
                   [c %2]
                   %1))
              [0 0]
              (range 1 1000000 2)))
;"Elapsed time: 8916.976351 msecs"
;[525 837799]

不过跑完才发现,压根没有缓存,仍然是那么慢,仔细分析了下,是因为缓存的时候只对collatz-cnt-memo的参数做了缓存,并没有对collatz-cnt函数的参数做缓存。于是,写出了另一个版本:

(def collatz-cnt-memo2 
  (memoize (fn [x]
             (if (= 1 x)
               1
               (if (even? x) 
                 (inc (collatz-cnt-memo2 (/ x 2)))
                 (inc (collatz-cnt-memo2 (inc (* 3 x)))))))))

看起来很完美,每次调用函数的时候,在尾部递归调用自己,而collatz-cnt-memo2函数又是缓存了的,效率应该提升很多。等等,似乎,这个并不是尾递归调用,会不会……StackOverflowError!!!试试(collatz-cnt-memo2 837799)果然如此。那,能否用recur来替换掉内部的递归呢?我自己试了下,几乎很难同时用recurmemoize来实现,比较接近一点的实现是不使用memoize函数,而是自己用宏实现一个类似的缓存机制(这样的做法显然不够优雅)。联想到前面的trampoline函数,可以尝试写出这样的版本:

(def collatz-cnt-memo3 
  (memoize (fn [x c]
             (if (= 1 x)
               c
               (if (even? x) 
                 #(collatz-cnt-memo3 (/ x 2) (inc c))
                 #(collatz-cnt-memo3 (inc (* 3 x)) (inc c)))))))
(def collatz-cnt-memo3 (partial trampoline collatz-cnt-memo3))

似乎,解决了StackOverflow的问题,然而,这个函数并没有实现真正意义上的缓存,因为函数内部迭代的时候,传入了两个参数xc,显然我们希望缓存的是fn [x]而不是fn [x c],但是,如果只传一个参数x,又没法做到尾递归(最后需要一个inc操作递归的返回值,使得count + 1),似乎,陷入了一个怪圈……

关于如何一步步优化这个问题的clojure代码,可以看这里(确实要比C++和python的代码都要慢很多)。接下来转向另外一个话题。

Y Combinator

看了一个周末,对自己的智商产生了怀疑……😂😂😂感觉,理解了是怎么回事,并没有体会到其中的精髓,建议看看wikipedia

Reference