再帰関数をループで表現してエラーを回避する

#はじめに
再帰関数はコンパクトに書けて便利ですが,言語の仕様などによって定められた再帰回数をこえてしまうとエラーになってしまいます
そのようなときは再帰関数はループに書き直すことでエラーを回避できます
特に幅優先探索で代用したくないような状況では重宝します

#使用環境
私のパソコン(Windows10 ,BCC32)だとOSが勝手に動作を停止させてしまうので
クラウドでコンパイル実行できるCodingGround の c++ を利用させてもらいました

Coding Ground
https://www.tutorialspoint.com/codingground.htm

gccのバージョンは以下の通りです

gcc version 4.8.5 20150623 (Red Hat 4.8.5-4) (GCC)

#考察に使うプログラムについて
1行目に幅と高さが空白区切り,
2行目からはデータとして0と1がスペース区切りで与えられている
このデータに4近傍(縦横)で隣接した1の島がいくつあるかを数えるプログラム
データの最大サイズは1000x1000として
受け取ったデータは保持しなくてもいいものとします

#再帰関数を使った例

island1.cpp

#include <iostream>
using namespace std;

int search(int i,int w,int h,char data[1000000]){
  if(data[i]=='1'){
    data[i]='0';
    if((i%w)!=0)     search(i-1,w,h,data);
    if((i%w)!=(w-1)) search(i+1,w,h,data);
    if((i/w)!=0)     search(i-w,w,h,data);
    if((i/w)!=(h-1)) search(i+w,w,h,data);
    return 1;
  }
  return 0;
}

int main(void){
  char data[1000000];
  int w,h;
  int count=0;
  cin >> w >> h;
  for(int i=0;i<w*h;i++){
    cin >> data[i];
  }
  for(int i=0;i<w*h;i++){
    count += search(i,w,h,data);
  }

  cout << count << endl;
  return 0;
}

結果(100x100オール1)

1

結果(1000x1000オール1)

Segmentation fault (core dumped)

1000x1000のオール1なのでこのときの最大の深さは1000000になります
このように深さが深くなるとエラーになってしまいます

#再帰関数を展開した例

island2.cpp

#include <iostream>
using namespace std;

#define RIGHT  0
#define LEFT   1
#define DOWN   2
#define UP     3
#define END    4


int main(void){
  char data[1000000];
  int w,h;
  int count=0;
  cin >> w >> h;
  for(int i=0;i<h*w;i++){
      cin >> data[i];
  }

  for(int i=0;i<h*w;i++){
    if(data[i]=='1'){
      while(true){
        /* marking start-point */
        if(data[i]=='1') data[i]=END;

        /* search */
        if((i%w)!=0)     if(data[i-1]=='1'){ data[--i]=RIGHT;      continue;}
        if((i%w)!=(w-1)) if(data[i+1]=='1'){ data[++i]=LEFT;       continue;}
        if((i/w)!=0)     if(data[i-w]=='1'){ data[i-w]=DOWN; i-=w; continue;}
        if((i/w)!=(h-1)) if(data[i+w]=='1'){ data[i+w]=UP;   i+=w; continue;}

        /* dead end */
        if(data[i]==RIGHT)  {data[i]='0';i++;continue;}
        if(data[i]==LEFT)   {data[i]='0';i--;continue;}
        if(data[i]==DOWN)   {data[i]='0';i+=w;continue;}
        if(data[i]==UP)     {data[i]='0';i-=w;continue;}

        /* terminate */
        if(data[i]==END)    {data[i]='0';count++;break;}
      }
    }
  }

  cout << count << endl;
  return 0;
}

再帰関数では一つ上の関数の保持する情報で戻っていましたが
一つ上の関数というものはないのでデータ自体に呼び出し元の情報を書きます
袋小路に来たら'0'に書き換えて呼び出し元に戻ります

結果(100x100オール1)

1

結果(1000x1000オール1)

1

このようにエラーを回避できました
#まとめ

• 再帰関数で書かれたプログラムは呼び出し元を記録しておくことによってループで書き替えられる
• エラーの原因となるので,再帰する数が不明の場合あるいは最大呼び出し数を超過する場合はループで書くほうが望ましい
• ただしループで書く場合は無限ループに入った際停止しないので使うときは注意が必要である