Lisp语言中,循环不像Java提供forwhile等语法,经典用法还是使用递归,clojure也有提供loop循环。在clojure中,递归、循环息息相关的工具recur,它的存在跟clojure实现在jvm之上有所关系,其原因也跟Java为什么有forwhile等语法相关。


  • recur是什么?怎么用?

recur相对于clojure的宏和函数来说,是个十分底层的程序控制操作,用于循环或递归。可以在不消耗堆栈的情况下,回到函数或循环体的最顶端。

例如在函数中使用recur实现递归:

1
2
3
4
5
6
;实至名归的尾递归!
(defn my_dec [x]
(if (< x 0)
x
;如果大于0,则回到my_dec,重新进入
(recur (dec x))))

又或者是loop循环:

1
2
3
4
5
;看起来还不如上面的递归呢!~
(loop [x 100]
(if (< x 0)
x
(recur (dec x))))

recur一定要放在结尾位置!不然clojure编译时会报错!比如我在my_dec [x]if包多一层int会怎样?
1
2
3
4
5
(defn my_dec [x]
(int (if (< x 0)
x
(recur (dec x)))))
;CompilerException java.lang.UnsupportedOperationException: Can only recur from tail position
显然编译不了,异常信息告诉你,你的recur不是放在结束位置,因为if返回值之后还有其他动作。
  • 为什么尾递归不是真正的尾递归?

上面的递归递减的例子才是真正的尾递归!为啥?

ok!在定义函数有个计算阶乘的例子。

1
2
3
4
5
6
7
(letfn [(factorial [x]
(factorial_2 (- x 1) x))
(factorial_2 [x y]
(if (< x 1)
y
(factorial_2 (- x 1) (* x y))))]
#(factorial %))

如果在Java中实现“尾递归”,我可以这样写:

1
2
3
4
5
public int factorial(int x, int sum) {
if (x < 2)
return sum;
return factorial(x - 1, sum * x);
}

如果用Java的循环,可以这样写:

1
2
3
4
5
6
7
//jvm没有实现尾递归优化支持,一大半原因是有了for等循环体,就觉得没必要吧。
public int factorial(int x) {
int y = 1;
for(;x > 1; x--)
y = y * x;
return y;
}

需要先知道的是,jvm不知道为毛,一直不想实现尾调用优化;所以int factorial(x, sum)虽然代码是尾递归格式,但并没什么卵用,这对于运行在它上面的函数式编程语言也是个坑!

正因为如此,在jvm上运行的clojure自然支持不了factorial[x y]这样的隐式尾递归,但提供了recur这个十分底层的工具(类似于goto),让我们显示地表示出尾递归。顺便说一句,同样运行在jvm的scala实现了尾递归,虽然十分有限,只支持严格尾递归,不明白clojure为啥也不搞一个。

  • clojure还有其他循环

尽管recur能帮你实现高效的尾递归,但依然需要谨慎,适当时候才使用。并不是因为有副作用,而是clojure提供了支持某些循环的宏,例如dotimesdoseqwhile(他们底层也是recur),这已经能够满足大多时候的需求了。

1
2
3
4
5
6
7
(dotimes [i 10]
(println "number:" i))
(def j 10)
(while (> j 0)
(println "number:" j)
(def j (dec j)))