C,C++,Javaとかをメインとしてやってる人が関数型について
「関数型は変数の値変更を良しとしない言語だから再帰関数を多用するよー」
って聞くと、即座に思い浮かぶ懸念は、
１．えっ、再帰関数多用って関数呼び出しコストどうするのよ？重いよねそれ？
２．えっ、再帰関数多用すると何処でスタックオーバーフローするか分からないし怖いよ。
だと思うんですよ（私はそうでした）。 Scalaは関数型も書ける言語なのでどうなのかというと結論からいうと
「大丈夫。気にすんな」
です。 Scalaでは「末尾再帰の最適化」がサポートされています。再帰関数の最後で自分自身を呼び出すようにすればコンパイル時に最適化されるのです（単純にwhileみたいに置き換えられる）。 ですので、
・関数呼び出しコスト
・スタックオーバーフロー
は大丈夫なのです。
論より証拠。
◆テストコード１
単純に数値カウントアップするだけ
非再帰
var i = 0
while(i <= high){
i += 1
}
再帰
def countUp(now: Int,high: Int):Int={
if(now <= high) countUp(now+1, high) else now
}
val i = countUp(0,high)
◆テストコード２
下限値(low)から上限値(high)までの合計値を求めるコード
非再帰
var sum = 0
var i = low
while(i <= high){
sum += i
i += 1
}
println("sum="+sum)
再帰
def sumRange(sum: Int,now: Int,high: Int):Int={
if(now <= high) sumRange(sum+now,now+1,high) else sum
}
val sum = sumRange(0,low,high)
println("sum="+sum)
で、ベンチマーク取ってみる
object CompRecursive{
import scala.testing.Benchmark
def main(args:List[String]){
//カウントアップバージョン
test1(100000000)
//合計計算バージョン
test2(0,100000000)
}
//テスト１：ただのカウントアップ
def test1(high: Int){
println("countUp")
val benchmarkNoRecursive = new Benchmark{
def run={
var i = 0
while(i <= high){
i += 1
}
println("count="+i)
}}
println("非再帰関数バージョン処理時間="+benchmarkNoRecursive.runBenchmark(1)(0)+"(/ms)")
val benchmarkRecursive = new Benchmark{
def run={
def countUp(now: Int,high: Int):Int={
if(now <= high) countUp(now+1, high) else now
}
val i = countUp(0,high)
println("count="+i)
}}
println("再帰関数バージョン処理時間="+benchmarkRecursive.runBenchmark(1)(0)+"(/ms)")
}
//テスト２：合計求める
def test2(low: Int,high: Int){
println("calculate sum")
val benchmarkNoRecursive = new Benchmark{
def run={
var sum = 0
var i = low
while(i <= high){
sum += i
i += 1
}
println("sum="+sum)
}}
println("非再帰関数バージョン処理時間="+benchmarkNoRecursive.runBenchmark(1)(0)+"(/ms)")
val benchmarkRecursive = new Benchmark{
def run={
def sumRange(sum: Int,now: Int,high: Int):Int={
if(now <= high) sumRange(sum+now,now+1,high) else sum
}
val sum = sumRange(0,low,high)
println("sum="+sum)
}}
println("再帰関数バージョン処理時間="+benchmarkRecursive.runBenchmark(1)(0)+"(/ms)")
}
}
CompRecursive.main(List(""))
私の環境だとこうなった
countUp
count=100000001
非再帰関数バージョン処理時間=93(/ms)
count=100000001
再帰関数バージョン処理時間=63(/ms)
calculate sum
sum=987459712
非再帰関数バージョン処理時間=141(/ms)
sum=987459712
再帰関数バージョン処理時間=110(/ms)
マジかよ再帰使ったほうが速いっ。
