関数型プログラミング入門(3) - 再帰関数

3回めです。今回は再帰関数について。とりあえずFPinScala P-26のフィボナッチ数列があるのでそれをやってみます。

まずはScalaでフィボナッチ数列を列挙してみましょう。

[scala]
object Fibonacci{
def fib(n: Int): Int = {
//@annotation.tailrec
def f(a: Int): Int = a match {
case n if n < 2 =>; n
case n => f(n-2) + f(n-1)
}
f(n)
}

def main(arg: Array[String]): Unit ={
println( (1 to 20).map(fib).mkString(", ") )
}
}
[/scala]

出力結果:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765

FPinScalaでは末尾最適化に触れていたのでここでもちょっと脇道にそれて末尾最適化に触れましょう。

@annotation.tailrec

という意味深なアノテーションがコメントアウトされていますね。これを外してコンパイルするとコンパイルエラーになります。

Error:(8, 24) could not optimize @tailrec annotated method f: it contains a recursive call not in tail position
 case n => f(n-2) + f(n-1)
 ^

@tailrecとは何なんでしょうか。これは、末尾最適化が行われない場合にコンパイルエラーとするためのアノテーションです。だから末尾最適化って何だよ!!というのはつまり・・・。

みなさんはプログラミングを学ぶ過程の何処かでループ方式の書き方と再帰方式の書き方を勉強しましたよね。その時に勉強したことを思い出してください。「ループは可読性が落ちるけど高速で(スタック)メモリ消費量も少ない」「再帰は可読性は上がるけど(スタック)メモリ消費量が多い」と勉強したのではないでしょうか。

末尾最適化と言うのは、コンパイラが再帰を裏でループに書きなおしてくれる最適化のことです。ですので、可読性を保ちつつメモリ消費量を抑え、かつ高速な処理を期待できます。ただしこれが適用されるためには関数の末尾が「再帰関数を呼んでいるだけ」でないといけません。関数fibの末尾の一部は

[scala]
case n => f(n-2) + f(n-1)
[/scala]

となっています。2回関数を呼んでそれを足し算しています。これでは末尾最適化が効きません。そこで、末尾最適化が効くように下記のように書きなおしてみました。一つ前の値を引数として保持するやり方です。

[scala]
object Fibonacci{
def fib(n: Int): Int = {
//@annotation.tailrec
def f(a: Int): Int = a match {
case n if n < 2 => n
case n => f(n-2) + f(n-1)
}
f(n)
}

def fib2(n: Int): Int = {
@annotation.tailrec
def f(n: Int, curr: Int, prev: Int): Int = n match {
case 0 => prev
case m => f(m-1, curr + prev, curr)
}
f(n, 1, 0)
}

def main(arg: Array[String]): Unit ={
println( (1 to 20).map(fib).mkString(", ") )
println( (1 to 20).map(fib2).mkString(", ") )
}
}
[/scala]

実行結果

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765

同じ結果が出力されました。

さて、ここまで説明してきませんでしたが、以下の部分はどうなっているんでしょうか。

[scala]
(1 to 20).map(fib).mkString(", ")
[/scala]

ここで、map関数にfib関数を渡しています。引数に関数を渡せるような関数を高階関数といいます。map関数はこの場合はIntを受け取って任意の型Aを出力するような関数を引数に取り、IntからAへの写像を適用(マッピング)します。

もう少し丁寧に説明すると、(1 to 20)の部分では1, 2, 3, 4, ... , 20という数列(Range)を生成しています。mapは先に述べたとおり元の型(ここではInt)から任意の型Aへのマッピングを行いますが、Int => Intな関数が渡されたのでコンパイラはこの文脈でのmapはIntからIntへの変換を行うのだと型を推論します。よって、mapが返す値はIntの数列になります。

次の回では高階関数に焦点を当てて行きたいと思います。