Q&A
回答ありがとうございます。CreateRoute（）を通らなくなる条件を考えればよかったのですね。再帰＝数が減っていくという思い込みがありわかりませんでした。
前提・実現したいこと
迷路を作ろうと思いプログラムを見ていたのですがあるＨＰで見つけた方法でわからないところがありました。再帰を使って壁を掘っているらしいのですが
↓のプログラムは
１．CreateRoute()で穴を掘ってその中のCancreate()で掘れるかどうかを判断して終わったら
２．outputMaze()で実際の描写をしていくというものです。
問題はCreateRouteの中でCreateRouteを使っているので再帰していることはわかりますが終了の方法がわかりません。実行すると描写されましたが、どうやって終わっているのかが理解できませんでした。
再帰関数は関数の中で関数を使うもので、終了条件を決めておいてループしないということが大事そうというのがわかるくらいです。このプログラムではどのような条件でCreateRouteを終了させているのでしょうか？よろしくおねがいします。
発生している問題・エラーメッセージ
エラーメッセージ
該当のソースコード
java
1 2import java.util.ArrayList; 3import java.util.Collections; 4 5public class Maze { 6 static final int height =55,width = 59; 7 public static void main(String[]args){ 8 int[][]maze=new int[height][width]; 9 int row=maze.length/2,col=maze[0].length/2; 10 maze[row][col]=1; 11 ArrayList<Integer>direction=new ArrayList<Integer>(); 12 direction.add(0); 13 direction.add(1); 14 direction.add(2); 15 direction.add(3); 16 createRoute(maze,row,col,direction); 17 outputMaze(maze); 18 } 19 public static void createRoute(int[][]maze,int row,int col,ArrayList<Integer>direction){ 20 Collections.shuffle(direction); 21 for(int i=0;i<direction.size();i++){ 22 if(canCreate(maze,direction.get(i),row,col)){ 23 switch(direction.get(i)){ 24 case 0: 25 maze[row][col-1]=1; 26 maze[row][col-2]=1; 27 col=col-2; 28 break; 29 case 1: 30 maze[row][col+1]=1; 31 maze[row][col+2]=1; 32 col=col+2; 33 break; 34 case 2: 35 maze[row+1][col]=1; 36 maze[row+2][col]=1; 37 row=row+2; 38 break; 39 case 3: 40 maze[row-1][col]=1; 41 maze[row-2][col]=1; 42 row=row-2; 43 break; 44 default: 45 break; 46 } 47 direction.add(0); 48 direction.add(1); 49 direction.add(2); 50 direction.add(3); 51 createRoute(maze,row,col,direction); 52 } 53 } 54 } 55 static boolean canCreate(int[][]maze,int direction,int row,int col){ 56 switch(direction){ 57 case 0: 58 if(col-2<=0){ 59 return false; 60 }else{ 61 if(maze[row][col-2]==0){ 62 return true; 63 }else{ 64 return false; 65 } 66 } 67 case 1: 68 if(col+2>=maze[0].length-1){ 69 return false; 70 }else{ 71 if(maze[row][col+2]==0){ 72 return true; 73 }else{ 74 return false; 75 } 76 } 77 case 2: 78 if(row+2>=maze.length-1){ 79 return false; 80 }else{ 81 if(maze[row+2][col]==0){ 82 return true; 83 }else{ 84 return false; 85 } 86 } 87 case 3: 88 if(row-2<=0){ 89 return false; 90 }else{ 91 if(maze[row-2][col]==0){ 92 return true; 93 }else{ 94 return false; 95 } 96 } 97 default: 98 } 99 return false; 100 } 101 public static void outputMaze(int[][]maze){ 102 for(int i=0;i<maze.length;i++){ 103 for(int j=0;j<maze[i].length;j++){ 104 if(maze[i][j]==0){ 105 System.out.print("□"); 106 }else{ 107 System.out.print(" "); 108 } 109 } 110 System.out.println(); 111 } 112 } 113} 114
試したこと
再帰関数で理解できたのはこの式だけで終了条件を決めて最終的に値が決まるよう式を作ることが必要だと思いましたが上記のプログラムではどのあたりが終了条件になっているのか理解できませんでした。
fanction(int n){
if(n==0){
return 1;
}
return fanction(n-1)n;
}
n=3なら
fanction(3)
3fanction(2)
32fanction(1)
321=6
補足情報（FW/ツールのバージョンなど）
回答3件
0
ベストアンサー
createRoute() の骨格は次のようになってます。
java
1public static void createRoute( ... ){ 2 Collections.shuffle(direction); 3 for(int i=0;i<direction.size();i++){ 4 if(canCreate(maze,direction.get(i),row,col)){ 5 ... 6 createRoute(maze,row,col,direction); 7 } 8 } 9 } 10}
このプログラムではどのような条件でCreateRouteを終了させているのでしょうか？
4 方向全てに対して canCreate(...) が false になった場合に
createRoute(...) の再帰呼出がされなくなる
と考えるとよいです。
投稿2018/02/25 00:19
総合スコア22324
0
createRouteが呼び出されてるのはif(canCreate(maze,direction.get(i),row,col)){}文の中ですよね。
なのでこのif文が偽の場合 ＝ 迷路がcanCreateできなくなった場合、このif文の中はスルーされるので、それ以上createRouteは呼び出されることはありません。
投稿2018/02/24 20:15
総合スコア158
0
再帰の記述はありますが、ifブロックの中なので必ずしも再帰することはありません。（実際の再帰はこんなものです）
ついでに、ご提示の階乗関数の場合は次のような処理になります。結果は一緒ですが。
×
fanction(3)
3fanction(2)
32fanction(1)
32*1=6
↓
〇
fanction(3)
3fanction(2)
32fanction(1)
321fanction(0)
321*1=6
投稿2018/02/24 22:32
総合スコア4830
回答ありがとうございます。答えだけでできてると思っていました。fanction(0)の前の１をかけることも動作を正確に知るために考えないといけないですね。
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2018/02/25 16:57
2018/02/26 22:36