This code is iterative in nature. Please make it recursive in nature. public cla
ID: 3700886 • Letter: T
Question
This code is iterative in nature. Please make it recursive in nature.
public class Maze
{
final int N = 4;
/* For printing the solution matrix
sol[N][N] */
void printSolution(int sol[][])
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
System.out.print(" " + sol[i][j] +
" ");
System.out.println();
}
}
/* to check if whether direction x,y are valid*/
boolean isSafe(int maze[][], int x, int y)
{
// if (x,y outside ) return false
return (x >= 0 && x < N && y >= 0 &&
y < N && maze[x][y] == 1);
}
boolean solveMaze(int maze[][])
{ int sol[][] = {{0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0} };
if (solveMazeUtil(maze, 0, 0, sol) == false)
{
System.out.print("Solution doesn't exist");
return false;
}
printSolution(sol);
return true;
}
/* function to solve Maze problem*/
boolean solveMazeUtil(int maze[][], int x, int y,
int sol[][])
{
// if (x,y is goal) return true
if (x == N - 1 && y == N - 1)
{
sol[x][y] = 1;
return true;
}
// Check if maze[x][y] is valid
if (isSafe(maze, x, y) == true)
{
// mark x,y as part of solution path
sol[x][y] = 1;
/* Move forward in x direction */
if (solveMazeUtil(maze, x + 1, y, sol))
return true;
/* If moving in x direction doesn't give
solution then Move down in y direction */
if (solveMazeUtil(maze, x, y + 1, sol))
return true;
/* Backtrack*/
sol[x][y] = 0;
return false;
}
return false;
}
public static void main(String args[])
{
Maze rat = new Maze();
int maze[][] = {{1, 0, 0, 0},
{1, 1, 0, 1},
{0, 1, 0, 0},
{1, 1, 1, 1}
};
rat.solveMaze(maze);
}
}
Explanation / Answer
The code is Recursive only. Where did you see this as Iterative . ? There is NO Loops here.
In the solveMazeUtil function we can see that the function calls itself solveMazeUtil(maze, x, y + 1, sol)).
Hence the program is Recursive in Nature.
Thanks, let me know if you need any more information.