1. はじめに
最近、関数型言語で再帰を書く機会があり。
ようやく理屈が少しだけ分かったので、大好きなJavaでやってみました。
2. Javaの再帰??
そもそも手続き型のJavaで再帰を書くことはあるのか？
周りの先輩エンジニアたちに聞いてみました。
2.1 アンケート
Q. 「Javaで再帰書くことってありますか？」
Aさん 「書けるけど、書かないといけない理由が無いと書かない。」
Bさん 「業務では書かない。」
Cさん 「変に書くと、メモリ食ってスタックオーバーフローするよ。」
2.2 アンケート結果
A. 「書かない」
もし効果的に書けるケースがあれば、コメント欄で教えていただけると嬉しいです！
3. とはいえやってみる
書かないとはわかりましたが、出来るならやってみたいですね。
と、いうわけで。Listの長さをintで返すlengthメソッドを実装してみました。
length(List) : int ← こんなん
3.1 やってみた
こんな感じになりました。
public static int length(List list) {
if (list.isEmpty()) {
return 0;
} else {
list.remove(0);
return length(list) + 1; // ここでもっかい自分自身を呼び出し
}
}
動かしてみましたが、ちゃんとできてました！
3.2 短くしてみた
調べてみると三項演算子使ってることが多かったので。
書いてみると、半数以下の行になりました。
ですが、可読性は低そう。。
public static int length(List list) {
return list.isEmpty() ? 0 : length(list) + 1;
}
しかし、動かしてみたところ。。
3.3 あれがおきた
↑の三項演算子の方のlengthメソッドを動かしてみたところ。。
Exception in thread "main" java.lang.StackOverflowError
at qiita.Recursion.length(Recursion.java:26)
at qiita.Recursion.length(Recursion.java:26)
at qiita.Recursion.length(Recursion.java:26)
at qiita.Recursion.length(Recursion.java:26)
...
4. StackOverflow
でました!!
[Java 再帰] で検索するとこのエントリーがよく出ますね！
スタックオーバーフローだ!!
(Listの中身を消し忘れていたので当然ですね)
4.1 スタックオーバーフローって？
再帰呼び出しを続けた結果、
**「メモリを使い切ってしまった」**的なエラーであることは、何となくは想像できます。
折角なので、今回はもう少し深くまで考えてみたいです。
4.2 コールスタック
プログラム中に再帰を呼び出す問題点の一つに、
- 再帰呼び出しを一回行うごとにコールスタックを一つ消費する必要がある。
と、いう事があるらしいです。
コールスタックぅ？
コールスタックとは新たな作業を始めるためのスペースだと思ってください。
人が並んで座れる長机だと考えるとわかりやすいかもしれません。このスペースがなくなるまで(つまり、隣に人が座れなくなるまで)再帰を続けるとスタックオーバーフローというエラーが起こります。
ジャパネットに電話した時にお話しする人とは関係ないようですね。
4.3 つまり
JVM内のPermanent領域から、OSのスタック領域にメソッド情報がガンガン送られてきて。
スタック領域が一杯になってしまう。というエラーなんですね。(なんでしょうかね。。？)
はじめは、「ガベージコレクションは仕事しないの？」と、思ったのですが。
GCってJVMのNew領域とOld領域をホニャラララしてくれるものだったから、仕事のしようが無いということですね。(なんでしょうかね。。？)
というかこのへんやっぱりよくわかってないんで、ちゃんと勉強しなきゃですね。
5. まとめ
Javaで再帰を書いてみて、よくセットで言われるスタックオーバーフローについて考えてみました。
特に、結論とかは無いので。もしここまで読んでいただいた人がいらっしゃったら時間を無駄にさせてしまったかと思います。。
ありがとうございます！！
参考
http://rn4ru.com/blog/posts/2014/Feb/14/tail-recursion/
http://promamo.com/?p=2828