末尾再帰最適化でスタックオーバーフローを回避する
1. 再帰関数の問題
末尾再帰最適化を理解する前に、まずは再帰関数が持つ問題点について理解します。以下のように自分自身を呼び出す関数を再帰関数と呼びますが、この再帰関数はStackOverflowになる可能性があります。
def factRecursive(n :Int): Int = {
if (n == 1) n
else n * factRecursive(n - 1)
}
これは階乗を求めるscalaの再帰関数の例ですが、自分の環境ではn=20000程でStackOverflowが起きてプログラムが終了してしまいます。
Exception in thread "main" java.lang.StackOverflowError
at Sample$.factRecursive(test.scala:14)
at Sample$.factRecursive(test.scala:14)
at Sample$.factRecursive(test.scala:14)
at Sample$.factRecursive(test.scala:14)
at Sample$.factRecursive(test.scala:14)
at Sample$.factRecursive(test.scala:14)2. StackOverflowとは
タスクを実行する時、スレッド毎に確保されたスタックと言われる領域に、関数の戻り先アドレスの情報や、引数、ローカル変数の情報が記録されます。CPUはスタックがどのアドレスから始まるのかをスタックポインタ(SP)として保存しますが、どこまで確保されているかを知りませんので、残りのスタック容量を超えたデータを追加することができてしまいます。 すると他の用途で確保されているメモリ空間を破壊してしまい、例外が起きたり最悪の場合はシステムが終了します。この状態をStackOverflowと呼びます。
3. なぜ再帰関数でStackOverflowが起こるのか
Stackに確保(PUSH)したメモリは通常関数が終了した時点で解放(POP)されます。再帰関数の場合には、関数呼び出し自体をスタックに積み上げる必要があります。したがって一つの関数で確保するメモリ容量が小さくても、関数のコール数との積算ではStack容量を超えてしまいます。
4. 末尾再帰最適化とは
関数の最後の呼び出しが自身の関数になっている再帰関数のことです。再帰関数をこの形式に書き換えることで、StackOverflowが発生しないコードに最適化することができるようになります(実際にはコンパイラが自動的にやってくれます) 。 一番最初に紹介した階乗を求めるプログラムを末尾再帰関数に書き直したものは以下のようになります。これは再帰関数でありながらStackOverflowが起きません。
@tailrec
def factTailRecursive(n :Int, a:Int): Int = {
if (n == 0) a
else factTailRecursive(n - 1, a * n)
}
実際に、このコードがどのような最適化されるのかを末尾再帰とそうでないコードを比較して確認してみます。このScalaコードをコンパイルしたclassファイルをjadで逆コンパイルしたものが以下になります。
jad Sample\$.class
再帰関数(末尾再帰では無い)を逆コンパイルした結果
三項演算子に書き換わっていますがその他は、記述した内容と同じだということがわかります。
public int factRecursive(int n)
{
return n != 1 ? n * factRecursive(n - 1) : n;
}
末尾再帰を逆コンパイルした結果
再帰関数からループ(while)に書き換わっていることがわかります。この処理であれば、関数呼び出しをスタックに積み上げる必要が無いので、StackOverflowになることはありません。
public int factTailRecursive(int n, int a)
{
while(n != 0)
{
a *= n;
n = n - 1;
}
return a;
}
5. まとめ
再帰関数を記述するとStackOverflowが発生する可能性がありますが、特定の言語であればコンパイラが末尾再帰最適化を行なってくれるので、気にしなくてもよくなります。再帰関数は、使い所によっては可読性が悪くなることもありますがループで書くよりもシンプルに記述できる場面も多くありますので、もしお使いの言語で対応しているのであれば導入してみてはどうでしょうか？
6. [付録] 末尾再帰最適化が使える言語
#scala ◯
デフォルトで有効になっています。@tailrecを関数に付けると、再帰関数が、再帰末尾になっていない場合にはコンパイルエラーにすることができるので、必ず付けるようにするのが良いと思います。
#kotlin ◯
有効です。
#ruby △
デフォルトでは無効です。tailcall_optimizationオプションを有効にすると利用可能になります。
#javascript △
ES6からは、実装仕様として要求されています。また、Babelではトランスパイル時に最適化するようになっています。
#golang ×
残念ながら使えません。 gonutsを眺める限り特定の場合では最適化されるという記述がありましたので、試して見ましたが使えないようです。また内部の開発者が今後も対応する気は無いと明言していましたので、期待できなさそうです。
#java ×
残念ながら使えません。