How to build a spiral square matrix using recursion?

Question

I wanted to build a spiral square matrix using recursion. I can build a spiral square matrix using an iterative method as shown below:

void main() { int initial_direction = UP , n = MAX , p = 1 ; /* intial_direction is set to UP because we need to start moving right */ int r ,c , a[MAX][MAX]; int row_right = 0 , column_down = n-1 , row_left = n-1 , column_up = 0 ; clrscr (); //Set all elements of the matrix to 0 for(r = 0 ; r < MAX ; r++) { for(c = 0 ; c < MAX ; c++) a[r][c] = 0 ; } //Generate elements of the spiral matrix while(p != n*n+1) { if(initial_direction == UP) { //Move RIGHT r = row_right++ ; for(c = 0 ; c < n ; c++) { if(a[r][c] == 0) a[r][c] = p++; } initial_direction = RIGHT ; } else if(initial_direction == RIGHT) { //Move down c = column_down-- ; for(r = 0 ; r < n ; r++) { if(a[r][c] == 0) a[r][c] = p++; } initial_direction = DOWN ; } else if(initial_direction == DOWN) { //Move left r = row_left-- ; for(c = n-1 ; c >= 0 ; c--) { if(a[r][c] == 0) a[r][c] = p++; } initial_direction = LEFT ; } else if(initial_direction == LEFT) { //Move up c = column_up++; for(r = n-1 ; r >= 0 ; r--) { if(a[r][c] == 0) a[r][c] = p++; } initial_direction = UP ; } } //Print the matrix printf("\n\n"); for(r = 0 ; r < MAX ; r++) { for(c = 0 ; c < MAX ; c++) printf("%4d ",a[r][c]); printf("\n"); } } 

I wanted to create the same matrix using recursion: Here is the code I used:

 #include <stdio.h> #include <stdlib.h> #include <stdbool.h> bool s[5][5] = {0}; int counter; typedef enum { right = 0, down, left, up }c_flag; c_flag flag; int last; int build_matrix(int a[5][5],int i,int j, c_flag flag) { int ret; if (i < 0 || i>=5 || j < 0 || j >= 5) { if (last == right) { flag = down; last = flag; } if (last == down) { flag = left; last = flag; } if (last == left) { flag = up; last = flag; } if (last == up) { flag = left; last = flag; } return false; } if (s[i][j] == true) { if (last == right) { flag = down; last = flag; } if (last == down) { flag = left; last = flag; } if (last == left) { flag = up; last = flag; } if (last == up) { flag = left; last = flag; } return false; } if(s[i][j] == false) { s[i][j] = true; a[i][j] = ++ counter; } if (flag == right) { ret = build_matrix(a,i,j+1,right); //if (!ret) // return false; } flag = down; last = flag; if (flag == down) { ret =build_matrix(a,i+1,j,down); //if (!ret) // return false; } flag = left; last = flag; if (flag == left) { ret = build_matrix(a,i,j-1,left); //if (!ret) // return false; } flag = up; last = flag; if (flag == up) { ret = build_matrix (a,i-1,j,up); //if (!ret) // return false; } flag = right; last = flag; return false; } int main() { int i, j, n = 5; int k, ret; //printf("Enter N to construct square matrix \n"); //scanf("%d",&n); int a[5][5] = {0}; k = n/2 + n%2; for (i = 0; i < k; i++) { ret = build_matrix(a,i,i,right); } for(i = 0; i < n; i++) { for(j = 0; j < n; j++) printf("%d",a[i][j]); printf("\n"); } return 0; } 

I exit the above as:

 1 2 3 4 5 16 19 22 25 6 15 18 21 24 7 14 17 20 23 8 13 12 11 10 9 

instead

 1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9 

The problem is that the checkbox is not set correctly, I do not know inside which the recursion call flag is violated. Please use one help using recursion.

Answer 1

 #include <stdio.h> void build_matrix(int msize, int a[msize][msize], int size, int value){ int i, row, col; if(size < 1) return; row = col = (msize - size) / 2; if(size==1){ a[row][col] = value; return; } for(i=0;i<size-1;++i) a[row][col++] = value++;//RIGHT for(i=0;i<size-1;++i) a[row++][col] = value++;//DOWN for(i=0;i<size-1;++i) a[row][col--] = value++;//LEFT for(i=0;i<size-1;++i) a[row--][col] = value++;//UP build_matrix(msize, a, size-2, value); } int main(){ int size; printf("input size : "); scanf("%d", &size); int a[size][size]; build_matrix(size, a, size, 1); for(int r=0;r<size;++r){ for(int c=0;c<size;++c) printf("%3d ", a[r][c]); printf("\n"); } return 0; } 

Answer 2

Working code without separation and just recursion:

 #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #define N 20 bool s[N][N] = {0}; int counter; typedef enum { right = 0, down, left, up }c_flag; c_flag flag; int build_matrix(int a[N][N],int i,int j, c_flag flag) { int ret; if (i < 0 || i>=N || j < 0 || j >= N || s[i][j] == true) return false; if(s[i][j] == false && a[i][j] == 0) { s[i][j] = true; a[i][j] = ++ counter; } if (flag == right) ret = build_matrix(a,i,j+1,right); flag = down; if (flag == down) ret =build_matrix(a,i+1,j,down); flag = left; if (flag == left) ret = build_matrix(a,i,j-1,left); flag = up; if (flag == up) ret = build_matrix (a,i-1,j,up); flag = right; if (flag == right) ret = build_matrix(a,i,j+1,right); return false; } int main() { int i, j; int k, ret; //printf("Enter N to construct square matrix \n"); //scanf("%d",&n); int a[N][N] = {0}; k = N/2 + N%2; build_matrix(a,i,i,right); for(i = 0; i < N; i++) { for(j = 0; j < N; j++) { if (!(a[i][j] < 100)) printf("%3d ",a[i][j]); else if(a[i][j] < 10) printf("00%d ",a[i][j]); else printf("0%d ",a[i][j]); } printf("\n"); } return 0; }