Open1
再帰を使った実装について。
NoboNobo
ここでRustの圧勝な比較記事。
Goは再帰的実装に関する最適化をあえて採用していません。
一般的なGopherは深い再帰に関する実装はループに置き換えます。
例えばこのfib関数
func fib(n uint64) uint64 {
switch n {
case 0:
return 0
case 1:
return 1
default:
return fib(n-1) + fib(n-2)
}
}
以下のようにループに書きなおせます。
func fib(n uint64) uint64 {
if n == 0 {
return 0
}
var a, b uint64 = 0, 1
for i := uint64(1); i < n; i++ {
a, b = b, a+b
}
return b
}
しかも、行数も同じ。
結局RustもLLVMが適合する時以外特に再帰に関する最適化はなさそうです。
再帰を使った実装は段数の制約を明言するか最適化がかかるのを確認して採用する技術です。
意外と適用範囲の狭い技術であることは認識されておくと良いかもしれません。
Haskell、Scala、Erlangなどは末尾再帰最適化を持っているので、多くの再帰実装で負荷が軽くなることが期待できますが、そうでない言語処理系で再帰で実装するような対象はかなり限定的です。
フォルダツリーの走査実装では再帰が使われますが、例えば「パス全体で4096バイト」「各ファイル名は255バイトまで」というような制約があるから、深さに実質的な制限があります。
再帰実装採用の際は 「段数の制約を明言するか最適化がかかるのを確認」 が良いでしょう。