Clojure的recur special form尾递归优化

Clojure中的recur special form是一种进行显式的尾递归优化的语法. 这个语法特性在其他语言中很少出现, 所以值得特别讨论一下.

简单递归

简答递归也叫平凡递归, 线性递归. 就是我们平时最常见到的递归形式, 一个函数内部调用它自己. 简单递归和迭代在语义上是等价的, 任何递归都可以翻译成同等含义的迭代形式. 但是递归会消耗栈. 会有递归深度的限制.

每次递归, 当前函数的局部变量都会制造一份新拷贝, 而代码都会操作这些新创建的变量, 因此每次调用只是操作属于该次调用的数据, 而不会相互影响. 或者说是immutable的. 这是函数式的特点之一, 为此在functional programming当中, 递归优于迭代, 这样做的代价是栈的消耗.

简单的递归中, 当递归深度增加, 栈溢出是不可避免的. 换句话说, 简单递归只能用在递归深度比较小的时候适合使用.

一个简单的经典例子是计算阶乘.

 
 
user=> (defn fact [n]
        (if (= n 1)
            1
            (*' n (fact (- n 1 )))
        )
)
 
(fact 4)
#'user/fact
user=> user=> 24
user=> (fact 60000)
StackOverflowError   user/fact (NO_SOURCE_FILE:44)
user=>
 
 

注意这里的乘法函数式*', 这是auto-promoting的数学函数, 会自动将Int型的运算变成BitInt型的计算. 因为阶乘运算会算出非常巨大的整数, 如果是普通的*, 在栈溢出之前就会抛出ArithmeticException integer overflow的错误.

尾递归

递归当中有一种特殊类型的递归对函数式语言特别重要, 就是尾递归. 当递归调用是函数的最后一个语句的时候, 称之为尾递归.

上面的阶乘函数并不是尾递归, 最后一句代码是加法操作. 下面是一个简单的尾递归例子.

 
(defn recurseme [n]
   (if (= n 0)   
     ()
     (do 
       (println (str n "th loop"))
       (recurseme (- n 1))
     )
   )
)
 

尾递归的一大特点是, 当调用发生之后, 当前函数的局部变量将不会再次被用到, 即这些内存是没有必要保留的. 可以通过简单的方法消除这种内存浪费, 这就是尾递归优化.

这里有很好的解释: tail recursion

自动尾递归优化

如果编译器足够智能, 可以自动的识别出尾递归并且优化之. 一个例子是Scheme语言, 他提供了一个通用的尾递归优化的功能. 但是并非所有编程语言和编译器都有这个功能. 特别是命令式编程语言或编译器. 一般不支持或者只是作为一个可选功能.

因为命令式语言中迭代优于递归, 和函数式正好相反.

JVM和尾递归优化

Clojure是建立在JVM之上的函数式编程语言. JVM通用性和庞大而丰富的类库使他成为一个理想的实现平台. 很多新的编程语句都是运行在JVM之上的.

但是JVM不支持尾递归, JVM一开始就是为命令式语言设计的系统, 并没有优先考虑函数式语言的需求. 这对要在JVM之上实现函数式语言的需求而言非常不利. 对命令式语言而言, 递归用的本来你就很少, 尾递归可能更少, 所以这不成一个问题.

而对函数式语言而言, 尾递归优化是一个重要到不能忽略的问题.

Scala和Clojure都是建立在JVM之上的支持函数式编程的语言. 对这个问题这两种语言就采取了不同的策略.

Scala提供的是隐式的尾递归优化, 就是编译器会自动识别尾递归, 如果判断是可以优化的就会默认进行优化. Clojure则是提供显式的尾递归优化.

Clojure的recur special form

Clojure中form是任何可以求值的对象, 包括列表, 向量, map, 数字, 关键字, 符号等等. 而special form是有自己特殊语法的form.

Clojure用于显式的尾递归优化的special form是recur.

Clojure不会隐式的对尾递归进行优化, 程序员必须明确的指出哪些是尾递归, 并通过使用recur来进行优化, recur会将一个尾递归转换为一个不需要消耗栈的循环.

如果我们将上面的阶乘函数变成尾递归形式并用recur优化, 会像这样

 
(defn fact [n] 
  (loop [current n acc  1]
    (if (= 1 current) 
      acc
      (recur (- current 1) (*' acc  current))
    )
  )
)
(fact 6000)
(fact 4)
 
 

Clojure这么做的原因是什么? 我们可以先看看隐式的尾递归会导致什么问题. 问题在于你不确定编译器是否真的如你所愿的那样进行优化. 有时候你认为应该优化的地方, 编译器不会这么做.

因为正确的找出哪些地方的调用是尾递归有时候并不是那么容易. 这样就可能出现一种情况, 程序员希望编译器做优化, 但是递归调用点的位置写错了, 那么编译器不会进行优化, 但是又不会有任何警告和错误. 编译器只会把他当成普通的递归.

显式的则不同, 如果使用recur的地方, 编译器发现并不是一个尾递归, 就会报错.

这里有个简单的函数

 
(defn recurseme [n]
   (if (= n 0)   
     ()
     (do 
       (println (str n "th loop"))
       (recurseme (- n 1))
     )
   )
)
 

这个递归只是模拟一个循环, 每次打印一条消息, 这是一个尾部递归.

优化也非常简单

 
(defn recurseme [n]
   (if (= n 0)   
     ()
     (do 
       (println (str n "th loop"))
       (recur  (- n 1))
     )
   )
)
 

但是下面的不是尾递归

 
(defn recurseme [n]
  (println
   (if (= n 0)   
     ()
     (do 
       (println (str n "th loop"))
       (recurseme  (- n 1))
     )
   )
  )
)
 

如果用recur去优化他, 得到的错误会是

 
CompilerException java.lang.UnsupportedOperationException: Can only recur from tail position, compiling:(NO_SOURCE_PATH:60:8)
 

这提供给程序员一个改正错误的机会. 较新的Scala中也提供了类似的功能, 提供了一个@tailrec注解, 加了此标记的函数如果编译器无法优化则会报错. 算是对隐式优化的弥补.