Recursion in JVM

最近、Clojureに入門しようとしていて、『プログラミングClojure』を読んでいる。

関数型言語では再帰をよく使うことになるはずだが、JVMで動く言語をほとんど書いたことがない(Javaのテストコードを書いたことがある程度)ので、JVMがスタックをどう扱うのかよくわかっていない。いくつかフィボナッチ数を求める例を挙げる。

予想どおりだが、nが大きくなるとStackOverflowErrorになる。

Clojureの関数呼び出しは常にスタックフレームを作りスタック領域を使うので、スタック消費型と呼ばれる。スタックフレームはnに対し指数的に増加するので、nが大きいとJVMのスタックを使い尽くす。

良さそうに見えるが、JVMはtail-call optimizationしないので、nが大きくなるとStackOverflowErrorになる。

『プログラミングClojure』の第2版によると、今のところ、JVM上で動くプログラミング言語で、自動でtail-call optimizationする言語は存在しないようだ。

詳細は理解できていないが、明示的にrecurと書けばJVMが最適化し、先程までStackOverflowErrorが出ていた大きさのnでも結果が返ってくる。

複数のフィボナッチ数を求めたい場合、計算途中をキャッシュしておきたくなる。値をいくつキャッシュするか、あるいはどの値をキャッシュするかは関数を実装する側ではなく、呼び出し側に責務があるべきである。呼び出し側が必要な範囲を取得する例を遅延シーケンスで実践してみる。

lazy-seqマクロで遅延シーケンスが生成させる。この関数が呼ばれて初めて(cons n (lazy-seq-fibo b n))が実行されるという意味である。下の例は10番目のフィボナッチ数を求めたものである。

遅延シーケンスもスタックやヒープを消費しない訳ではないが、シーケンス全体の長さに比例したリソースを消費することはないという点が重要である。

--

--

Software engineer

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store