庄周梦蝶

生活、程序、未来
   :: 首页 ::  ::  :: 聚合  :: 管理

详解Clojure的递归(上)—— 直接递归及优化

Posted on 2010-07-14 22:03 dennis 阅读(4851) 评论(4)  编辑  收藏 所属分类: 动态语言javaClojure
    详解clojure递归(上)
    详解clojure递归(下)

    递归可以说是LISP的灵魂之一,通过递归可以简洁地描述数学公式、函数调用,Clojure是LISP的方言,同样需要递归来扮演重要作用。递归的价值在于可以让你的思维以what的形式思考,而无需考虑how,你写出来的代码就是数学公式,就是函数的描述,一切显得直观和透明。如果你不习惯递归,那只是因为命令式语言的思维根深蒂固,如x=x+1这样的表达式,从数学的角度来看完全不合法,但是在命令式语言里却是合法的赋值语句。

   递归可以分为直接递归和间接递归,取决于函数是否直接或者间接地调用自身。如果函数的最后一个调用是递归调用,那么这样的递归调用称为尾递归,针对此类递归调用,编译器可以作所谓的尾递归优化(TCO),因为递归调用是最后一个,因此函数的局部变量等没有必要再保存,本次调用的结果可以完全作为参数传递给下一个递归调用,清空当前的栈并复用,那么就不需要为递归的函数调用保存一长串的栈,因此不会有栈溢出的问题。在Erlang、LISP这样的FP语言里,都支持TCO,无论是直接递归或者间接递归。

   但是由于JVM自身的限制,Clojure和Scala一样,仅支持直接的尾递归优化,将尾递归调用优化成循环语句。例如一个求阶乘的例子:
   
;;第一个版本的阶乘函数
(defn fac [n]
          (
if (= 1 n)
              
1
             (
* n (fac (dec n)))))

   第一个版本的阶乘并非尾递归,这是因为最后一个表达式的调用是一个乘法运算,而非(fac (dec n)),因此这个版本的阶乘在计算大数的时候会导致栈溢出:
user=> (fac 10000)
java.lang.StackOverflowError (NO_SOURCE_FILE:
0)

   将第一个版本改进一下,为了让最后一个调用是递归调用,那么我们需要将结果作为参数来传递,而不是倚靠栈来保存,并且为了维持接口一样,我们引入了一个内部函数fac0:
  
  ;;第二个版本,不是尾递归的“尾递归”
  (defn fac [n]
           (defn fac0 [c r]
              (
if (= 0 c)
                  r
                  (fac0 (dec c) (
* c r))))
           (fac0 n 
1))

   这个是第二个版本的阶乘,通过将结果提取成参数来传递,就将fac0函数的递归调用修改为尾递归的形式,这是个尾递归吗?这在Scala里,在LISP里,这都是尾递归,但是Clojure的TCO优化却是要求使用recur这个特殊形式,而不能直接用函数名作递归调用,因此我们这个第二版本在计算大数的时候仍然将栈溢出:
user=> (fac 10000)
java.lang.StackOverflowError (NO_SOURCE_FILE:
0)

   在Clojure里正确地TCO应该是什么样子的呢?其实只要用recur在最后调用那一下替代fac0即可,这就形成我们第三个版本的阶乘:
  ;;第三个版本,TCO起作用了
  (defn fac [n]
           (defn fac0 [c r]
              (
if (= 0 c)
                  r
                  (recur (dec c) (
* c r))))
           (fac0 n 
1))

    此时你再计算大数就没有问题了,计算(fac 10000)可以正常运行(结果太长,我就不贴出来了)。recur只能跟函数或者loop结合在一起使用,只有函数和loop会形成递归点。我们第三个版本就是利用函数fac0做了尾递归调用的优化。
   
    loop跟let相似,只不过loop会在顶层形成一个递归点,以便recur重新绑定参数,使用loop改写阶乘函数,这时候就不需要定义内部函数了:
;;利用loop改写的第四个版本的阶乘函数
(defn fac [n]
           (loop [n n r 
1]
                (
if (= n 0)
                    r
                    (recur (dec n) (
* n r)))))

   loop初始的时候将n绑定为传入的参数n(由于作用域不同,同名没有问题),将r绑定为1,最后recur就可以将新的参数值绑定到loop的参数列表并递归调用。

   Clojure的TCO是怎么做到的,具体可以看看我前两天写的这篇博客,本质上是在编译的时候将最后的递归调用转化成一条goto语句跳转到开始的Label,也就是转变成了循环调用。

   这个阶乘函数仍然有优化的空间,可以看到,每次计算其实都有部分是重复计算的,如计算(fac 5)也就是1*2*3*4*5,计算(fac 6)的1*2*3*4*5*6,如果能将前面的计算结果缓存下来,那么计算(fac 6)的时候将更快一些,这可以通过memoize函数来包装阶乘函数:
;;第五个版本的阶乘,缓存中间结果
(
def fac (memoize fac))

第一次计算(fac 10000)花费的时间长一些,因为还没有缓存:
user=> (time (fac 10000)) 
"Elapsed time: 170.489622 msecs"


第二次计算快了非常多(其实没有计算,只是返回缓存结果):
user=> (time (fac 10000))
"Elapsed time: 0.058737 msecs"

    可以看到,如果没有预先缓存,利用memoize包装的阶乘函数也是快不了。memoize的问题在于,计算(fac n)路径上的没有用到的值都不会缓存,它只缓存最终的结果,因此如果计算n前面的其他没有计算过的数字,仍然需要重新计算。那么怎么保存路径上的值呢?这可以将求阶乘转化成另一个等价问题来解决。
    我们可以将所有的阶乘结果组织成一个无穷集合,求阶乘变成从这个集合里取第n个元素,这是利用Clojure里集合是lazy的特性,集合里的元素如果没有使用到,那么就不会预先计算,而是等待要用到的时候才计算出来,定义一个阶乘结果的无穷集合,可以利用map将fac作用在整数集合上,map、reduce这样的高阶函数返回的是LazySeq:
 (def fac-seq (map fac (iterate inc 0)))

   (iterate inc 0)定义了正整数集合包括0,0的阶乘没有意义。这个集合的第0项其实是多余的。
   查看fac-seq的类型,这是一个LazySeq:
user=> (class fac-seq)
clojure.lang.LazySeq

  求n的阶乘,等价于从这个集合里取第n个元素:
user=> (nth fac-seq 10)
3628800

  这个集合会比较耗内存,因为会缓存所有计算路径上的独立的值,哪怕他们暂时不会被用到。但是这种采用LazySeq的方式来定义阶乘函数的方式有个优点,那就是在定义fac-seq使用的fac函数无需一定是符合TCO的函数,我们的第一个版本的阶乘函数稍微修改下也可以使用,并且不会栈溢出:
(defn fac [n]
          (
if (<= n 1)
              
1
              (
* n (fac (dec n)))))

(
def fac (memoize fac))
(
def fac-seq (map fac (iterate inc 0)))
(nth fac
-seq 10000)


  因为集合从0开始,因此只是修改了fac的if条件为n<=1的时候返回1。至于为什么这样就不会栈溢出,有兴趣的朋友可以自己思考下。

    从这个例子也可以看出,一些无法TCO的递归调用可以转化为LazySeq来处理,这算是弥补JVM缺陷的一个办法。
   



评论

# re: 详解Clojure的递归(上)—— 直接递归及优化  回复  更多评论   

2010-07-16 13:34 by clojans
因为楼主是用memoize记住上一个数字的fac的结果,自然不需要去再计算他了,也可以是用lazy-seq实现
(defn lazy-fac
([]
(concat [0 1] (lazy-fac 0 1)))
([a b]
(let [n (+ a b)]
(lazy-seq
(cons n (lazy-fac b n))))))

(nth (lazy-fac) 100)

# re: 详解Clojure的递归(上)—— 直接递归及优化  回复  更多评论   

2010-12-29 09:15 by 热卖啦2
http://www.remaila.net/

# re: 详解Clojure的递归(上)—— 直接递归及优化  回复  更多评论   

2010-12-29 09:16 by 热卖啦4
http://www.easy518.com/

# re: 详解Clojure的递归(上)—— 直接递归及优化[未登录]  回复  更多评论   

2013-02-08 10:24 by Wind
问个问题, lazy只是推迟eval值, 对于下面的例子, 如果要取第100000个fac数, 仍然需要递归调用100000次, 为什么不会blew stack?

(defn lazy-fac
([]
(concat [0 1] (lazy-fac 0 1)))
([a b]
(let [n (+ a b)]
(lazy-seq
(cons n (lazy-fac b n))))))

(nth (lazy-fac) 100000)

只有注册用户登录后才能发表评论。


网站导航: