前回はメソッドの関数的な使い方について説明しました。今回は「再帰定義」について説明します。
関数定義の中で、その関数自身を呼び出すことを「再帰呼び出し (recursive call)」とか「再帰定義 (recursive definition)」といいます。関数の定義に自分自身を使うことができるなんて、何か特別な仕掛があるのではないかと思われるかもしれません。ところが、再帰定義は特別なことではありません。大昔のプログラミング言語ならばいざしらず、今では再帰呼び出しができないプログラミング言語のほうが珍しいでしょう。もちろん Scala の関数 (メソッド) も再帰呼び出しが可能です。
再帰定義というと、関数型言語の専売特許だと思われている方もいるでしょう。実際、Ｃ言語などの手続き型言語では、再帰定義を難しいテクニックの一つと思い込んでしまい、初心者の方は避けて通ることが多いように思います。再帰定義は、今まで説明した関数の呼び出しとまったく同じなので、難しく考える必要はありません。慣れるまでちょっと苦労するかもしれませんが、ポイントさえつかめば簡単に使いこなすことができます。
まずは簡単な例を見てみましょう。階乗を計算するプログラムです。階乗の定義を下図に示します。
階乗の定義からわかるように、n の階乗は n - 1 の階乗がわかれば求めることができます。実は、これをそのままプログラムすることができます。次の例を見てください。
scala> def fact(n: Int): BigInt = if (n == 0) 1 else n * fact(n - 1) def fact(n: Int): BigInt scala> for(i <- 0 to 20) println(fact(i)) 1 1 2 6 24 120 720 5040 40320 362880 3628800 39916800 479001600 6227020800 87178291200 1307674368000 20922789888000 355687428096000 6402373705728000 121645100408832000 2432902008176640000
関数 fact は引数 n が 0 であれば 1 を返し、そうでなければ n * fact(n - 1) の計算結果を返します。fact の定義で fact 自身を呼び出しています。これが再帰呼び出しです。
階乗と同じように再帰定義で表されるアルゴリズムはたくさんあります。階乗の計算は簡単なので、再帰呼び出しを使わなくても繰り返しでプログラムできますが、再帰で定義されるアルゴリズムのなかには、繰り返しに変換すると複雑なプログラムになってしまうものがあります。
このような場合は、素直に再帰定義を使ったほうがわかりやすいプログラムになり、間違いを犯す危険性が少なくなります。難しいアルゴリズムでも、再帰定義を使うと簡単にプログラムできる場合もあるのです。
それでは、再帰定義のポイントを説明しましょう。次の図を見てください。
┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐
│Call:1 │->│Call:2 │->│Call:3 │->│Call:4 │->│Call:5 │
│n:4 │ │n:3 │ │n:2 │ │n:1 │ │n:0 │
│value : 24│<-│value : 6 │<-│value : 2 │<-│value : 1 │<-│value : 1 │
└─────┘ └─────┘ └─────┘ └─────┘ └─────┘
図 : fact の再帰呼び出し（n:引数の値, value:返り値）
上図は関数 fact(4) の呼び出しを表したものです。最初の呼び出し (Call:1) では、引数 n の値は 4 なので n の値を 1 減らして fact を再帰呼び出しします。2 回目の呼び出しでは、引数 n の値に 3 が代入されます。ここで、最初に呼び出したときと、2 回目に呼び出したときでは、引数 n の値が違うことに注意してく
ださい。関数の引数は局所変数として扱われます。前回説明したように、局所変数には有効範囲（スコープ）があります。引数の場合、その関数が実行されている間だけ有効です。局所変数は関数呼び出しが行われるたびに新しく生成されて、そこに値が代入されます。そして、関数の実行が終了すると、生成された局所変数は廃棄されます。つまり、1 回目の呼び出しと 2 回目の呼び出しでは、引数 n は名前が同じでも異なる変数になるのです。ここが再帰呼び出しを理解するポイントの一つです。
プログラムを見ると変数 n は一つしかありませんが、再帰呼び出しが行われるたびに新しい変数 n が作られていくと考えてください。fact(4) を実行しているときの n は 4 であり、fact(3) を呼び出すときには、この n の値を書き換えるのではなく、新しい変数 n を用意して、そこに 3 を代入するのです。
同様に再帰呼び出しが行われ、5 回目の呼び出し (Call:5) で引数 n が 0 になります。このとき、if の then 節が実行され 1 が返されます。ここで再帰呼び出しが止まります。これを再帰呼び出しの「停止条件」といいます。ここが第 2 のポイントです。停止条件がなかったり、あってもその条件を満たさない場合、関数を際限なく呼び出すことになり、Scala であればプログラムの実行は途中で停止します。再帰呼び出しを使う場合は、この停止条件に十分注意してください。
fact(0) は 1 を返して fact(1) に戻ります。fact(1) を実行しているあいだ、引数 n の値は 1 です。したがって、fact(1) の返り値は 1 * 1 を計算して 1 となります。あとは同様に、再帰呼び出しした関数の返り値を使って値を計算し、最後に fact(4) の値 24 を求めることができます。
次は、負でない整数 a と b の最大公約数を求めるプログラムを「ユークリッド (Euclid) の互除法」で作ります。まず最初に、ユークリッドの互除法を説明します。
ユークリッドの互除法は簡単に証明できます。\(a\) と \(b\) の割り算を式 (1) で表します。
ここで、\(a\) と \(b\) の最大公約数を \(m\) とすると、\(a = m \times a', \ b = m \times b'\) となります。すると、式 (1) は式 (2) で表すことができます。
左辺は \(m\) で割り切れるので、右辺も \(m\) で割り切れる必要があります。\(q \times m \times b'\) は \(m\) で割り切れるので、\(r\) も \(m\) で割り切れることになります。つまり、\(m\) は \(b\) と \(r\) の公約数であることがわかります。\(b\) と \(r\) の最大公約数を \(m'\) とすると、式 (3) が成り立ちます。
次に、\(b = m' \times b'', \ r = m' \times r' \)として式 (1) に代入すると、式 (4) が成り立ちます。
右辺は \(m'\) で割り切れるので、\(a\) も \(m'\) で割り切れる必要があります。つまり、\(m'\) は \(a\) と \(b\) の公約数であることがわかります。したがって、式 (5) が成り立ちます。
式 (3) と (5) より \(m = m'\) となり、\(a\) と \(b\) の最大公約数は \(b\) と \(r\) の最大公約数に等しいことが証明されました。
あとは b を a とし、r を b にして同じ計算をすればいいわけです。この計算を繰り返し行うと、a と b はどんどん小さくなっていき、r = 0 になったときの b が最大公約数になります。
プログラムは再帰定義を使って簡単に作ることができます。次の例を見てください。
scala> def gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b) def gcd(a: Int, b: Int): Int scala> gcd(42, 30) val res7: Int = 6 scala> gcd(15, 70) val res8: Int = 5 scala> def lcm(a: Int, b: Int): Int = a * b / gcd(a, b) def lcm(a: Int, b: Int): Int scala> lcm(5, 7) val res9: Int = 35 scala> lcm(14, 35) val res10: Int = 70
関数 gcd は引数 a と b の最大公約数を求めます。b が 0 の場合は a を返します。これが再帰呼び出しの停止条件になります。そうでなければ、gcd を再帰呼び出しして、b と a % b の最大公約数を求めます。gcd はユークリッドの互除法の定義をそのままプログラムしただけです。このように、再帰定義を使うと簡単にプログラムを作ることができます。また、整数 a と b の最小公倍数 (lcm) は a * b / gcd(a, b) で求めることができます。
もうひとつ簡単な数値計算の例を示しましょう。フィボナッチ関数も再帰的に定義される関数です。
フィボナッチ関数も再帰定義を使えば簡単にプログラムできます。次の例を見てください。
scala> def fibo(n: Int): BigInt = if (n == 0 || n == 1) n else fibo(n - 1) + fibo(n - 2) def fibo(n: Int): BigInt scala> for (i <- 0 to 20) println(fibo(i)) 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765
関数 fibo は fact とは違い、自分自身を 2 回呼び出しています。これを「二重再帰」といいます。fibo の呼び出しをトレースすると下図のようになります。
f(5) ┬ f(4) ┬ f(3) ┬ f(2) ┬ f(1)
│ │ │ │
│ │ │ └ f(0)
│ │ └ f(1)
│ └ f(2) ┬ f(1)
│ │
│ └ f(0)
│
└ f(3) ┬ f(2) ┬ f(1)
│ │
│ └ f(0)
└ f(1)
図 : fibo のトレース
同じ値を何回も求めているため、効率はとても悪いのです。もちろん、高速に求める方法があるので、心配しないで下さい。
再帰定義のなかで、処理の最後で再帰呼び出しを行う場合を「末尾再帰 (tail recursion)」といいます。英語では tail recursion ですが、日本語では末尾再帰のほかに末端再帰とか終端再帰と呼ぶことがあります。末尾再帰は簡単な処理で繰り返しに変換できることが知られています。
関数型言語や論理型言語の Prolog では、プログラムをコンパイルもしくは実行するとき、末尾再帰を繰り返しに変換する処理系があります。この機能を「末尾再帰最適化」[*1] といいます。なかには Scheme [*2] のように、言語仕様に末尾再帰最適化を行うことを明記しているプログラミング言語もあります。
たとえば、階乗を計算する関数 fact を思い出してください。fact は最後に n と fact の返り値を乗算しているので、このプログラムは末尾再帰ではありません。これを末尾再帰に変換すると次のようになります。
scala> def facti(n: Int, a: BigInt): BigInt = if (n == 0) a else facti(n - 1, a * n) facti: (n: Int, a: BigInt)BigInt scala> for (i <- 0 to 20) println(facti(i, 1)) 1 1 2 6 24 120 720 5040 40320 362880 3628800 39916800 479001600 6227020800 87178291200 1307674368000 20922789888000 355687428096000 6402373705728000 121645100408832000 2432902008176640000
最後の再帰呼び出しで、facti の返り値をそのまま返しているので、このプログラムは末尾再帰になっています。これで階乗を計算できるなんて、ちょっと不思議に思われるかもしれません。そこが再帰呼び出しの面白いところです。このプログラムでは引数 a の使い方がポイントです。
たとえば facti(4) を実行すると、このプログラムでは 4 * 3 * 2 * 1 を計算します。このとき、計算の途中経過を引数 a に記憶しているのです。facti の呼び出しを下図に示します。
facti(4, 1)
| facti(3, 4)
| | facti(2, 12)
| | | facti(1, 24)
| | | | facti(0, 24)
| | | | => a の値 24 を返す
| | | => 24
| | => 24
| => 24
=> 24
図 : facti の動作
引数 a には計算途中の値が格納されていることがわかります。このような変数を「累算変数」とか「累算器」といいます。
関数型言語の場合、while文 や for文 などの繰り返しがないプログラミング言語があります。また、論理型言語 Prolog にも単純な繰り返しはありません。これらのプログラミング言語では、繰り返しのかわりに末尾再帰を使ってプログラミングを行い、末尾再帰最適化によりプログラムを高速に実行することができます。
なお、引数 a をデフォルト引数 (初期値 1) に指定すると、facti(n) で階乗を求めることができます。
scala> def facti(n: Int, a: BigInt = 1): BigInt =
| if (n == 0) a else facti(n - 1, a * n)
def facti(n: Int, a: BigInt): BigInt
scala> facti(10)
val res13: BigInt = 3628800
scala> facti(20)
val res14: BigInt = 2432902008176640000
末尾再帰最適化は Scala でも行われています。次の例を見てください。
scala> def sumOfInt(n: Int, m: Int): BigInt =
| if (n > m) 0 else n + sumOfInt(n + 1, m)
def sumOfInt(n: Int, m: Int): BigInt
scala> sumOfInt(1, 100)
val res15: BigInt = 5050
scala> sumOfInt(1, 1000)
val res16: BigInt = 500500
scala> sumOfInt(1, 10000)
=> スタックオーバーフロー
関数 sumOfInt を再帰定義でプログラムしました。ただし、これは末尾再帰ではありません。1 から 10000 までの和を求めると、スタックがオーバーフローしてプログラムの実行は停止します。
これを末尾再帰でプログラムすると次のようになります。
scala> def sumOfInt1(n: Int, m: Int, a: BigInt = 0): BigInt =
| if (n > m) a else sumOfInt1(n + 1, m, a + n)
def sumOfInt1(n: Int, m: Int, a: BigInt): BigInt
scala> sumOfInt1(1, 1000)
val res18: BigInt = 500500
scala> sumOfInt1(1, 10000)
val res19: BigInt = 50005000
scala> sumOfInt1(1, 100000)
val res20: BigInt = 5000050000
sumOfInt1 は末尾再帰になっていて、Scala の末尾再帰最適化により大きな値でもスタックオーバーフローせずに求めることができます。
今度は累算変数を使って、二重再帰を末尾再帰に変換してみましょう。フィボナッチ関数 fibo は二重再帰になっているので、とても時間がかかります。二重再帰を末尾再帰に変換すると、プログラムを高速に実行することができます。次の例を見てください。
scala> def fiboi(n: Int, a1: BigInt = 0, a2: BigInt = 1): BigInt =
| if (n == 0) a1 else fiboi(n - 1, a2, a1 + a2)
def fiboi(n: Int, a1: BigInt, a2: BigInt): BigInt
scala> for (i <- 0 to 20) println(fiboi(i))
0
1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
6765
累算変数 a1 と a2 の使い方がポイントです。現在のフィボナッチ数を変数 a1 に、ひとつ先の値を変数 a2 に格納しておきます。あとは a1 と a2 を足し算して、新しいフィボナッチ数を計算すればいいわけです。fiboi の呼び出しを図に示すと、次のようになります。
fiboi (5, 0, 1)
fiboi (4, 1, 1)
fiboi (3, 1, 2)
fiboi (2, 2, 3)
fiboi (1, 3, 5)
fiboi (0, 5, 8)
=> a1 の値 5 を返す
=> 5
=> 5
=> 5
=> 5
=> 5
図 : 関数 fibo の呼び出し
二重再帰では、同じ値を何回も求めていたため効率がとても悪かったのですが、このプログラムでは無駄な計算を行っていないので、値を高速に求めることができます。もちろん、末尾再帰になっているので、末尾再帰最適化を行う処理系では、プログラムをより高速に実行できるでしょう。
ところで、最大公約数を求める関数 gcd は末尾再帰になっています。Scala は末尾再帰最適化をサポートしているので、このままでも高速に実行することができますが、繰り返しに変換するのも簡単です。次の例を見てください。
scala> def gcdi(a: Int, b: Int): Int = {
| var x = a
| var y = b
| while (y > 0) {
| val z = x
| x = y
| y = z % y
| }
| x
| }
def gcdi(a: Int, b: Int): Int
scala> gcdi(42, 30)
val res22: Int = 6
scala> gcdi(15, 70)
val res23: Int = 5
関数 gcdi は引数 a, b の値を変数 x, y にコピーして、変数 x, y を書き換えることで最大公約数を求めています。再帰定義を使ったプログラムはユークリッドの互除法であることがすぐにわかりますが、繰り返しに変換するとプログラムは少しわかりにくくなると思います。また、Scala の引数は immutable なので、mutable な変数を用意する分だけ、プログラムはちょっと複雑になります。
繰り返しは再帰定義に比べると実行速度やメモリの消費量など効率の点で有利です。このため、何がなんでも繰り返しでプログラムしようとする方もいるでしょう。ところが、再帰定義を使うと簡単にプログラムできるが、繰り返しではとても複雑なプログラムになってしまう場合もあります。したがって、とくに問題がなければ再帰定義を繰り返しに変換する必要はないと思います。複雑なプログラムは、しばらくたつと書いた本人でさえ理解できなくなることがよくあります。わかりやすいプログラムがいちばんです
相互再帰とは、関数 foo が関数 bar を呼び出し、bar でも foo を呼び出すというように、お互いに再帰呼び出しを行っていることをいいます。関数型言語 (SML/NJ, OCaml など) では、相互再帰を定義するために専用の構文を使いますが、Scala は特別なことをしなくても相互再帰を行うことができます。
それでは簡単な例を示しましょう。次の例を見てください。
リスト : 相互再帰
object sample0301 {
def foo(n: Int): Boolean =
if (n == 0) true else bar(n - 1)
def bar(n: Int): Boolean =
if (n == 0) false else foo(n - 1)
}
このプログラムは関数 foo と bar が相互再帰しています。foo と bar が何をしているのか、実際に動かしてみましょう。
scala> :load sample0301.scala // defined object sample0301 scala> import sample0301._ scala> bar(3) val res0: Boolean = true scala> bar(2) val res1: Boolean = false scala> bar(1) val res2: Boolean = true scala> foo(3) val res3: Boolean = false scala> foo(2) val res4: Boolean = true scala> foo(1) val res5: Boolean = false
結果を見ればおわかりのように、foo は n が偶数のときに真を返し、bar は n が奇数のときに真を返します。なお、このプログラムはあくまでも相互再帰の例題であり、実用的なプログラムではありません。
もうひとつ、Scala には注意点があります。foo や bar に大きな値を与えるとスタックオーバーフローします。foo と bar はお互いに処理の末尾で呼び出されています。関数型言語、たとえば Scheme, SML/NJ, OCaml などでは、このような場合でも末尾再帰最適化が行われますが、Scala の場合、相互再帰の末尾再帰最適化は行われません。ご注意くださいませ。