遞歸很好用客情，但容易導(dǎo)致棧溢出(SystemStackError: stack level too deep)。
簡(jiǎn)單的解決方案有兩個(gè)衅谷，一個(gè)是把ruby的stack size調(diào)大椒拗，一個(gè)是用尾遞歸。
Stack level too deep
def factorial(n)
raise InvalidArgument, "negative input given" if n < 0
if n == 0
1
else
factorial(n - 1) * n
end
end
輸入比較小的時(shí)候会喝，代碼工作正常
irb> factorial(1_000).to_s.size
=> 2568
但當(dāng)我們把輸入變大的時(shí)候陡叠，就會(huì)報(bào)錯(cuò)
irb> factorial(100_000).to_s.size
SystemStackError: stack level too deep
解決方案 - 增加棧大小
我們可以增加ruby vm的棧大小玩郊。只要設(shè)置RUBY_THREAD_VM_STACK_SIZE這個(gè)環(huán)境變量就可以了。
export RUBY_THREAD_VM_STACK_SIZE=50000000
我們還可以通過(guò)RubyVM::DEFAULT_PARAMS這條命令查看原有的值枉阵。
不過(guò)译红，這種方式也不能完全解決問(wèn)題的，更好的方式是兴溜，使用尾遞歸侦厚。
尾遞歸
ruby默認(rèn)是不支持尾遞歸的，首先我們要先開(kāi)啟配置拙徽。
RubyVM::InstructionSequence.compile_option = {
tailcall_optimization: true,
trace_instruction: false
}
尾遞歸的實(shí)現(xiàn)如下:
def factorial_by_tail_call(n, accumulator = 1)
raise InvalidArgument, "negative input given" if n < 0
return accumulator if n == 0
return factorial_by_tail_call(n - 1, accumulator * n)
end
尾遞歸為什么沒(méi)有溢出刨沦？
簡(jiǎn)單來(lái)說(shuō)在factorial內(nèi)， factorial(n - 1) * n 必須要有n才能計(jì)算出結(jié)果膘怕，所以當(dāng)前這次執(zhí)行(procedure call)必須要存在內(nèi)存里想诅。
但factorial_by_tail_call卻不一樣，factorial_by_tail_call(n - 1, accumulator * n)不依賴任何其他變量岛心，可以直接被執(zhí)行来破，其實(shí)沒(méi)必要存在內(nèi)存里，所以可以被優(yōu)化忘古。
語(yǔ)言對(duì)尾遞歸的支持情況
首先尾遞歸優(yōu)化需要解釋器的支持徘禁。
ruby也是后來(lái)才支持的，但需要手動(dòng)開(kāi)啟髓堪。
java不支持送朱，clojure雖然不支持，但用recur達(dá)到了同樣的效果干旁。
最后驶沼，上個(gè)世紀(jì)的lisp是支持尾遞歸的！
