Clojure由于是基于JVM，同样无法支持完全的尾递归优化（TCO)，这主要是Java的安全模型决定的，可以看看这个
久远的bug描述。但是Clojure和Scala一样支持同一个函数的直接调用的尾递归优化，也就是同一个函数在函数体的最后调用自身，会优化成循环语句。让我们看看这是怎么实现的。
Clojure的recur的特殊形式（special form）就是用于支持这个优化，让我们看一个例子，经典的求斐波那契数：
(defn recur
-
fibo [n] (letfn [(fib [current next n] (
if
(zero
?
n) current ;recur将递归调用fib函数 (recur next (
+
current next) (dec n))))] (fib
0
1
n)))
recur-fibo这个函数的内部定义了一个fib函数，fib函数的实现就是斐波那契数的定义，fib函数的三个参数分别是当前的斐波那契数(current)、下一个斐波那契数(next)、计数器(n)，当计数器为0的时候返回当前的斐波那契数字，否则就将当前的斐波那契数设置为下一个，下一个斐波那契数字等于两者之和，计数递减并递归调用fib函数。注意，你这里不能直接调用(fib
next (
+
current next) (dec n))，否则仍将栈溢出。这跟Scala不同，Clojure是用recur关键字而非原函数名作TOC优化。 Clojure是利用asm 3.0作字节码生成，观察下recur-fibo生成的字节码会发现它其实生成了两个类，类似user$recur_fibo__4346$fib__4348和user$recur_fibo__4346，user是namespace,前一个是recur-fibo中的fib函数的实现，后一个则是recur-fibo自身，这两个类都继承自 clojure.lang.AFunction类，值得一提的是前一个类是后一个类的内部类，这跟函数定义相吻合。所有的用户定义的函数都将继承 clojure.lang.AFunction。 在这两个类中都有一个invoke方法，用于实际的方法执行，让我们看看内部类fib的invoke方法（忽略了一些旁枝末节）
1
//
access flags 1
2
public
invoke(Ljava
/
lang
/
Object;Ljava
/
lang
/
Object;Ljava
/
lang
/
Object;)Ljava
/
lang
/
Object;
throws
java
/
lang
/
Exception
3
L0
4
LINENUMBER
2
L0
5
L1
6
LINENUMBER
4
L1
7
L2
8
LINENUMBER
4
L2
9 ALOAD 310 INVOKESTATIC clojure/lang/Numbers.isZero (Ljava/lang/Object;)Z
11 IFEQ L3
12 ALOAD 113 GOTO L4
14
L5
15
POP
16
L3
17
ALOAD
2
18
L6
19
LINENUMBER
6
L6
20 ALOAD 121 ALOAD 222 INVOKESTATIC clojure/lang/Numbers.add (Ljava/lang/Object;Ljava/lang/Object;)Ljava/lang/Number;
23
L7
24
LINENUMBER
6
L7
25 ALOAD 326 INVOKESTATIC clojure/lang/Numbers.dec (Ljava/lang/Object;)Ljava/lang/Number;
27 ASTORE 328 ASTORE 229 ASTORE 130 GOTO L0
31
L4
32
L8
33
LOCALVARIABLE
this
Ljava
/
lang
/
Object; L0 L8
0
34
LOCALVARIABLE current Ljava
/
lang
/
Object; L0 L8
1
35
LOCALVARIABLE next Ljava
/
lang
/
Object; L0 L8
2
36
LOCALVARIABLE n Ljava
/
lang
/
Object; L0 L8
3
37 ARETURN
38
MAXSTACK
=
0
39
MAXLOCALS
=
0
首先看方法签名，invoke接收三个参数，都是Object类型，对应fib函数里的current、next和n。
关键指令都已经加亮，9——11行，加载n这个参数，利用Number.isZero判断n是否为0，如果为0，将1弹入堆，否则弹入0。IFEQ比较栈顶是否为0，为0（也就是n不为0)就跳转到L3，否则继续执行(n为0，加载参数1，也就是current，然后跳转到L4，最后通过ARETURN返回值current作结果。
指令20——22行，加载current和next，执行相加操作，生成下一个斐波那契数。
指令25-——26行，加载n并递减。
指令27——29行，将本次计算的结果存储到local变量区，覆盖了原有的值。
指令30行，跳转到L0，重新开始执行fib函数，此时local变量区的参数值已经是上一次执行的结果。
有的朋友可能要问，为什么加载current是用aload 1，而不是aload 0，处在0位置上的是什么？0位置上存储的就是著名的this指针，invoke是实例方法，第一个参数一定是this。
从上面的分析可以看到，recur干的事情就两件：覆盖原有的local变量，以及跳转到函数开头执行循环操作，这就是所谓的软尾递归优化。这从RecurExp的实现也可以看出来：
//
覆盖变量
for
(
int
i
=
loopLocals.count()
-
1
; i
>=
0
; i
--
) { LocalBinding lb
=
(LocalBinding) loopLocals.nth(i); Class primc
=
lb.getPrimitiveType();
if
(primc
!=
null
) { gen.visitVarInsn(Type.getType(primc).getOpcode(Opcodes.ISTORE), lb.idx); }
else
{ gen.visitVarInsn(OBJECT_TYPE.getOpcode(Opcodes.ISTORE), lb.idx); } }
//
执行跳转
gen.goTo(loopLabel);
recur分析完了，最后有兴趣可以看下recur-fibo的invoke字节码
1
L0
2
LINENUMBER
1
L0
3
ACONST_NULL
4
ASTORE
2
5 NEW user$recur_fibo__4346$fib__4348 6 DUP 7 INVOKESPECIAL user$recur_fibo__4346$fib__4348.<init> ()V
8
ASTORE
2
9
ALOAD
2
10
CHECKCAST user$recur_fibo__4346$fib__4348
11
POP
12
L1
13
L2
14
LINENUMBER
7
L2
15
ALOAD
2
16
CHECKCAST clojure
/
lang
/
IFn
17
GETSTATIC user$recur_fibo__4346.const__2 : Ljava
/
lang
/
Object;
18
GETSTATIC user$recur_fibo__4346.const__3 : Ljava
/
lang
/
Object;
19
ALOAD
1
20
ACONST_NULL
21
ASTORE
1
22
ACONST_NULL
23
ASTORE
2
24 INVOKEINTERFACE clojure/lang/IFn.invoke (Ljava/lang/Object;Ljava/lang/Object;Ljava/lang/Object;)Ljava/lang/Object;
25
L3
26
LOCALVARIABLE fib Ljava
/
lang
/
Object; L1 L3
2
27
L4
28
LOCALVARIABLE
this
Ljava
/
lang
/
Object; L0 L4
0
29
LOCALVARIABLE n Ljava
/
lang
/
Object; L0 L4
1
30
ARETURN
5——7行,实例化一个内部的fib函数。
24行，调用fib对象的invoke方法，传入3个初始参数。
简单来说，recur-fibo生成的对象里只是new了一个fib生成的对象，然后调用它的invoke方法，这也揭示了Clojure的内部函数的实现机制。
文章转自庄周梦蝶 ，原文发布时间 2010-07-11
相关资源：xodarap：Clojure中的无畏递归-源码
