def fib(n) return 1 if n == 0 || n == 1 return fib(n - 1) + fib(n - 2) end fib(40)
开启 TCO 版本：
RubyVM::InstructionSequence.compile_option = { :tailcall_optimization => true, :trace_instruction => false }
RubyVM::InstructionSequence.new(<<-EOF).eval def fib(n) return 1 if n == 0 || n == 1 return fib(n - 1) + fib(n - 2) end EOF
fib(40)
在我机器上第一个跑了 40s，第二个 35s。还是有一点儿效果的:-) ps：Ruby1.9 默认 TOC 是关闭的，只有通过 RubyVM::InstructionSequence.new.eval 的方法才能开启优化。
refs:
InstructionSequence.compile_option 是全局选项，后面的所有代码不需要 InstructionSequence.new 了。
只用特定参数编译一段代码，可以用 InstructionSequence.new src, file, path, line, opts （new 和 compile 是同一个方法）
opts = {
tailcall_optimization: false,
trace_instruction: false
}
iseq = RubyVM::InstructionSequence.compile <<-RUBY, nil, nil, nil, opts
def fib(n)
return 1 if n == 0 || n == 1
return fib(n - 1) + fib(n - 2)
end
RUBY
puts iseq.disasm
输出如下
== disasm: <RubyVM::InstructionSequence:<compiled>@<compiled>>==========
0000 putspecialobject 1
0002 putspecialobject 2
0004 putobject :fib
0006 putiseq fib
0008 send :"core#define_method", 3, nil, 0, <ic:0>
0014 leave
== disasm: <RubyVM::InstructionSequence:fib@<compiled>>=================
local table (size: 2, argc: 1 [opts: 0, rest: -1, post: 0, block: -1] s1)
[ 2] n<Arg>
0000 getlocal n ( 1)
0002 putobject 0
0004 opt_eq <ic:7>
0006 branchif 16
0008 getlocal n
0010 putobject 1
0012 opt_eq <ic:8>
0014 branchunless 21
0016 jump 18
0018 putobject 1
0020 leave
0021 putself ( 2)
0022 getlocal n
0024 putobject 1
0026 opt_minus <ic:9>
0028 send :fib, 1, nil, 8, <ic:3>
0034 putself
0035 getlocal n
0037 putobject 2
0039 opt_minus <ic:10>
0041 send :fib, 1, nil, 8, <ic:5>
0047 opt_plus <ic:11>
0049 leave
@hooopo 你那个例子速度变快的原因应该是 :trace_instruction => false 去掉了编译后的 trace 指令（默认 trace 是打开的）
这个例子不是尾递归，最后一个指令是 opt_plus，不是递归调用 send :fib （所有 opt_ 开头的指令都是为了优化特定 code pattern 的，opt_plus 相当于 send :+ 但为整数优化了）
不过尾调用优化和尾递归优化不同，尾递归优化把字节码里的某些递归变成循环，尾调用优化不改写字节码，但在运行的时候碰到 return method call 时就改写栈帧（或者说只把 send 指令改成 tail_send 指令），改写耗的时间往往比增长栈多，所以除了避免暴栈以外作用很微...
刚刚也是觉得 fib 这个例子不大好，记得就是 haskell 也是没办法直接将 fib 优化成循环的样子...
于是写了个 fact 的例子：
require 'date'
def prof
t0 = DateTime.now
yield
p (DateTime.now - t0).to_f
end
def fact(n)
r = 1
i = 1
while i <= n
r*=i
i+=1
end
return r
end
def fact0(n)
return 1 if n == 0 || n == 1
return n * fact0(n-1)
end
prof { fact(4000) }
prof { fact0(4000) }
RubyVM::InstructionSequence.compile_option = {
:tailcall_optimization => true,
:trace_instruction => false
}
def fact1(n)
return 1 if n == 0 || n == 1
return n * fact1(n-1)
end
def _fact2(r, n)
return r if n <= 1
return _fact2(r*n, n-1)
end
def fact2(n)
_fact2(1, n)
end
prof { fact1(4000) }
prof { fact2(4000)}
结果 fact2 最慢 = =
update: 调大数据 fact2 是最后一个报 stack overflow 的倒是...
这是《Erlang 编程指南》里的一段话：
关于Erlang性能的主要传说之一：Erlang中尾递归要比直接递归有效的多。在该语言初期也许是真的。但在对发行版7到12进行了优化之后，如果还继续认为尾递归让你的程序更有效率那就不再正确了。
难到不是说 Erlang 里非尾递归也会很有效率？
不是你说的只有程序员写成尾递归寒数编译器才能优化吧
问了一下 yufeng，回复——
实际上是这样的，递归用的堆内存，尾递归用的是栈的内存
所以总体现在性能差不多
除非递归的深度非常深
看起来 erlang 没有改造普通递归（我觉得也改不了），但是尾递归只能避免爆栈，对于性能没优势
