関数を関数の中から呼ぶと、どこからよばれたのかという記録がコールスタックというところにスタックされていきます。その限界についてしらべてみました。
なぜ調べたのか
先日アルゴリズムの勉強をしよう 第一回 深さ優先探索という記事の中でナンプレを解くプログラムを組みました。その中で Maximum call stack size exceededというエラー(訳すと最大コールスタックサイズを超えましたです)が起きました。結局直ったのですがなぜ起きたのか不気味だったので計算してみました。
関数の中から呼ぶとコールスタックというところにスタックされると先ほど書きました。そして深さ優先探索は関数から関数を呼ぶ(再帰呼び出し)を使うため、どんどんコールスタックが溜まります。コールスタックは限界容量があるのでサイズが大きくなるとこのエラーが起きます。
調べてみると、ブラウザによって若干違いがありました。Mac OS Xで検証しました。Google chromeでは17691回呼び出すとスタックオーバーします。Safariでは58251回呼び出すとスタックオーバーします。まあMacはOSレベルでSafariと連結してるらしいのでしょうがないです。
終わりに
意外なことにChromeでも17691回は再帰できるとわかりました。ということは普通に組む分には再帰を使えるということですね。これがわかって再帰を一々forループに直さなくても良いとわかり安心しました。
(再帰だと関数呼び出しコストがかかり速度が落ちるので速度出したい時はforループに直したほうがいいです)