-1
我正在研究鼠迷宮問題（你可以向右或向下移動，如果是1，並且沒有，如果是0）。我有問題，我的結果不會返回堆棧，我追蹤它，一切都很好，然後我改變了我的代碼，它的工作原理，我不理解我的跟蹤是不正確的。Java，在鼠迷宮上追蹤遞歸
我會發布3個版本的代碼，首先正確，然後2不正確。我的問題是關於每個遞歸代碼的適當跟蹤是什麼，以便我可以下次正確跟蹤自己的代碼，並明白我正確地跟蹤它以發現錯誤。
我應該提到的結果是可能的路徑數量達到[N-1] [M-1]
正確的代碼
import java.io.*;
import java.util.*;
class Solution {
public static int findpath(int [][] arr){
int row = 0;
int col = 0;
int result = 0;
return findpathHelper(arr, row, col, result);
}
public static int findpathHelper(int [][] arr, int row, int col, int result){
System.out.println(row);
System.out.println(col);
System.out.println();
if(col == arr[row].length-1 && row == arr.length-1){
System.out.println("Result: " +result);
return result+1;
}
if(row+1 != arr.length && arr[row+1][col] != 0){
result = findpathHelper(arr, row+1, col, result);
}
if(col+1 != arr[row].length && arr[row][col+1] != 0){
result = findpathHelper(arr, row,col+1, result);
}
return result;
}
public static void main(String[] args) {
int [][] path = {{1,1,1,1},
{0,1,1,1},
{1,0,0,1},
{1,1,1,1}};
System.out.println(findpath(path));
}
}
不正確的代碼1 即使在基本情況下更新之後，結果在調用堆棧上始終爲0 我只是在遞歸案例中刪除了'result ='
import java.io.*;
import java.util.*;
class Solution {
public static int findpath(int [][] arr){
int row = 0;
int col = 0;
int result = 0;
return findpathHelper(arr, row, col, result);
}
public static int findpathHelper(int [][] arr, int row, int col, int result){
System.out.println(row);
System.out.println(col);
System.out.println();
if(col == arr[row].length-1 && row == arr.length-1){
System.out.println("Result: " +result);
return result+1;
}
if(row+1 != arr.length && arr[row+1][col] != 0){
findpathHelper(arr, row+1, col, result);
}
if(col+1 != arr[row].length && arr[row][col+1] != 0){
findpathHelper(arr, row,col+1, result);
}
return result;
}
public static void main(String[] args) {
int [][] path = {{1,1,1,1},
{0,1,1,1},
{1,0,0,1},
{1,1,1,1}};
System.out.println(findpath(path));
}
}
錯誤代碼2 在基本情況我擺脫了回報，而是正在使用第一次調用棧中的返回+ = 1， 是1，但因爲它可以追溯到到堆棧返回到是0
import java.io.*;
import java.util.*;
class Solution {
public static int findpath(int [][] arr){
int row = 0;
int col = 0;
int result = 0;
return findpathHelper(arr, row, col, result);
}
public static int findpathHelper(int [][] arr, int row, int col, int result){
System.out.println(row);
System.out.println(col);
System.out.println();
if(col == arr[row].length-1 && row == arr.length-1){
System.out.println("Result: " +result);
result+=1;
}
if(row+1 != arr.length && arr[row+1][col] != 0){
return = findpathHelper(arr, row+1, col, result);
}
if(col+1 != arr[row].length && arr[row][col+1] != 0){
return = findpathHelper(arr, row,col+1, result);
}
return result;
}
public static void main(String[] args) {
int [][] path = {{1,1,1,1},
{0,1,1,1},
{1,0,0,1},
{1,1,1,1}};
System.out.println(findpath(path));
}
}
aditional的編輯 展望第二不正確的代碼，如果我添加了收益率=上個e遞歸的情況下，但不是基本的情況下，代碼仍然顯得很好 import java.io. ; import java.util。;
class Solution {
public static int findpath(int [][] arr){
int row = 0;
int col = 0;
int result = 0;
return findpathHelper(arr, row, col, result);
}
public static int findpathHelper(int [][] arr, int row, int col, int result){
System.out.println(row);
System.out.println(col);
System.out.println();
if(col == arr[row].length-1 && row == arr.length-1){
System.out.println("Result: " +result);
result+=1;
}
if(row+1 != arr.length && arr[row+1][col] != 0){
result = findpathHelper(arr, row+1, col, result);
}
if(col+1 != arr[row].length && arr[row][col+1] != 0){
result = findpathHelper(arr, row,col+1, result);
}
return result;
}
public static void main(String[] args) {
int [][] path = {{1,1,1,1},
{0,1,1,1},
{1,0,0,1},
{1,1,1,1}};
System.out.println(findpath(path));
}
}