庄周梦蝶

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

详解Clojure的递归(下)——相互递归和trampoline

Posted on 2010-08-22 13:52 dennis 阅读(3057) 评论(0)  编辑  收藏 所属分类: Clojure
    详解clojure递归(上)
    详解clojure递归(下)
   
    这篇blog拖到现在才写,如果再不写,估计就只有上篇没有下篇了,趁周末写一下。

    上篇提到了Clojure仅支持有限的TCO,不支持间接的TCO,但是有一类特殊的尾递归clojure是支持,这就是相互递归。且看一个例子,定义两个函数用于判断奇数偶数:
(declare my-odd? my-even?)
(defn my
-odd? [n]
      (
if (= n 0)
          false
         (my
-even? (dec n))))
(defn my
-even? [n]
      (
if (= n 0)
          true
         (my
-odd? (dec n))))

    这里使用declare做前向声明,不然在定义my-odd?的时候my-even?还没有定义,导致出错。可以看到,my-odd?调用了my-even?,而my-even?调用了my-odd?,这是一个相互递归的定义:如果n为0,那肯定不是奇数,否则就判断n-1是不是偶数,反之亦然。

    这个递归定义看起来巧妙,但是刚才已经提到clojure通过recur支持直接的TCO优化,这个相互递归在大数计算上会导致堆栈溢出:
user=> (my-odd? 10000)
java.lang.StackOverflowError (NO_SOURCE_FILE:
0)

user=> (my-even? 10000)
java.lang.StackOverflowError (NO_SOURCE_FILE:0)


    怎么解决呢?一个办法是转化成一个直接递归调用,定义一个parity函数,当偶数的时候返回0,当奇数的时候返回1:
(defn parity [n]
      (loop [n n par 
0]
            (
if (= n 0)
                par
                (recur (dec n) (
- 1 par)))))
user=> (parity 3)
1
user=> (parity 100)
0
user=> (parity 10000)
0
user=> (parity 10001)
1
   

    parity是直接的尾递归,并且使用了recur优化,重新定义my-odd和my-even就很简单了:
(defn my-even? [n] (= 0 (parity n)))
(defn my
-odd?  [n] (= 1 (parity n)))
   
    但是这样的方式终究不是特别优雅,相互递归的定义简洁优雅,有没有什么办法保持这个优雅的定义并且避免堆栈溢出呢?答案是trampoline,翻译过来是弹簧床,查看trampoline函数文档:
user=> (doc trampoline)
-------------------------
clojure.core
/trampoline
([f] [f 
& args])
  trampoline can be used to convert algorithms requiring mutual
  recursion without stack consumption. Calls f with supplied args, 
if
  any. If f returns a fn, calls that fn with no arguments, and
  continues to repeat, until the 
return value is not a fn, then
  returns that non
-fn value. Note that if you want to return a fn as a
  
final value, you must wrap it in some data structure and unpack it
  after trampoline returns.
   简单来说trampoline接收一个函数做参数并调用,如果结果为函数,那么就递归调用函数,如果不是,则返回结果,主要就是为了解决相互递归调用堆栈溢出的问题,查看trampoline的定义:
(defn trampoline
  ([f]
     (let [ret (f)]
       (
if (fn? ret)
          (recur ret)
          ret)))

   看到trampoline利用recur做了尾递归优化,原有的my-odd?和my-even?需要做一个小改动,就可以利用trampoline来做递归优化了:
(declare my-odd? my-even?)
(defn my
-odd? [n]
      (
if (= n 0)
          
false
         #(my
-even? (dec n))))
(defn my
-even? [n]
      (
if (= n 0)
          
true
         #(my
-odd? (dec n))))
 
   唯一的改动就是函数的末尾行前面加了个#,将递归调用修改成返回一个匿名函数了,使用trampoline调用my-even?和my-odd?不会再堆栈溢出了:
user=> (trampoline my-odd? 10000000)
false
user
=> (trampoline my-even? 10000)  
true
user
=> (trampoline my-even? (* 1000 1000))
true
  
   弹簧床这个名称很形象,一次调用就是落到弹簧床上,如果是函数,反弹回去再来一次,如果不是,本次表演结束。
   
 

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


网站导航: