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

    xiaoxiao2024-03-11  124

    详解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    文章转自庄周梦蝶  ,原文发布时间 2010-08-22 相关资源:新年快乐! python实现绚烂的烟花绽放效果
    最新回复(0)