再帰回数の限界

フラクタル図形のような自己相似図形を描くのに、再帰プログラムが、理にかなっていると思うのだが、多くのマンデルブロ集合プログラムは、再帰が使われていない。なにか不都合があるのだろうか。

簡単な例として、1+2+3+の再帰を考える。このプログラムは一見問題なさそうであるが、いざ実行してみると、値を増やしていくと、27000前後でstack　overflowのエラーを出す。関数から関数を呼び出すわけで、そのムダがちりつもになることは容易に総合できるが、意外と早く来た。
　まぁ、そういう理由でマンデルブロ集合も再帰プログラムではないのだろう。メリット少ないし。
　実行環境にかなり左右されるようで、実行の度に、エラーだったり、エラーでなかったりする。このあたり、うまくやるとコンパイラが、回避するコードに変換してくれるようだが、javaにはそういう機能はないらしい。

void setup() {
  print(f(27000));
}

int f(int n) {
  if (n<=0) {
    return 0;
  }
  return n+f(n-1);
}

再帰を使わずに描くと、こうなる。

int n=27000;
int s=0;
while(0<n){
  s+=n;
  n--;
}
print(s);

nはもっと大きくても問題ない。
計算結果は両者とも同じ。
計算時間は短すぎて計測不能。
※もちろんintの大きさを超えたら、おかしくなる。

よくあるフラクタルのコードは、この末尾再帰問題を回避したコードって、ことなんだろう。
オセロのコードなんかだと、再帰使うはずだけど、無限を目指すような分野では使えないってことね。

参考（末尾再帰最適化）