понимание возвратов (робота на сетке)

Question

Вот код для робота, который перемещается по сетке, которая предполагают, чтобы перейти от верхнего левого угла в правый нижний и найти уникальные способы достижения в правом нижнем углу:

public static int findNumPath(int row, int col){ 
int total = 0; 

//if grid[2][2] is reached, 1 path is found 
if(row == 2 && col == 2){ 
    return 1; 
} 
grid[row][col] = true; 
print(); 

if(col < 2 && grid[row][col+1] == false){ 
    System.out.println("inside 1st if" + " ,total= " + total); 
    total = total + findNumPath(row, col+1); 
} 
if(col > 0 && grid[row][col-1] == false){ 
    System.out.println("inside 2nd if" + " ,total= " + total); 
    total = total + findNumPath(row, col-1); 
} 
if(row < 2 && grid[row+1][col] == false){ 
    System.out.println("inside 3rd if" + " ,total= " + total); 
    total = total + findNumPath(row+1, col); 
} 
if(row > 0 && grid[row-1][col] == false){ 
    System.out.println("inside 4th if"+ " ,total= " + total); 
    total = total + findNumPath(row-1, col); 
} 

grid[row][col] = false; 
System.out.println("after making false" + " total=" + total); 
return total; 
} 

Вот результат:

true false false 
false false false 
false false false 

inside 1st if ,total= 0 
true true false 
false false false 
false false false 

inside 1st if ,total= 0 
true true true 
false false false 
false false false 

inside 3rd if ,total= 0 
true true true 
false false true 
false false false 

inside 2nd if ,total= 0 
true true true 
false true true 
false false false 

inside 2nd if ,total= 0 
true true true 
true true true 
false false false 

inside 3rd if ,total= 0 
true true true 
true true true 
true false false 

inside 1st if ,total= 0 
true true true 
true true true 
true true false 

inside 1st if ,total= 0 
after making false total=1 
after making false total=1 
after making false total=1 
inside 3rd if ,total= 1 
true true true 
false true true 
false true false 

inside 1st if ,total= 0 
inside 2nd if ,total= 1 
true true true 
false true true 
true true false 

inside 4th if ,total= 0 
true true true 
true true true 
true true false 

after making false total=0 
after making false total=0 
after making false total=1 
after making false total=2 
inside 3rd if ,total= 2 
after making false total=3 
after making false total=3 
inside 3rd if ,total= 3 
true true false 
false true false 
false false false 

inside 1st if ,total= 0 
true true false 
false true true 
false false false 

inside 3rd if ,total= 0 
inside 4th if ,total= 1 
true true true 
false true true 
false false false 

after making false total=0 
after making false total=1 
inside 2nd if ,total= 1 
true true false 
true true false 
false false false 

inside 3rd if ,total= 0 
true true false 
true true false 
true false false 

inside 1st if ,total= 0 
true true false 
true true false 
true true false 

inside 1st if ,total= 0 
after making false total=1 
after making false total=1 
after making false total=1 
inside 3rd if ,total= 2 
true true false 
false true false 
false true false 

inside 1st if ,total= 0 
inside 2nd if ,total= 1 
true true false 
false true false 
true true false 

inside 4th if ,total= 0 
true true false 
true true false 
true true false 

after making false total=0 
after making false total=0 
after making false total=1 
after making false total=3 
after making false total=6 
inside 3rd if ,total= 6 
true false false 
true false false 
false false false 

inside 1st if ,total= 0 
true false false 
true true false 
false false false 

inside 1st if ,total= 0 
true false false 
true true true 
false false false 

inside 3rd if ,total= 0 
inside 4th if ,total= 1 
true false true 
true true true 
false false false 

inside 2nd if ,total= 0 
true true true 
true true true 
false false false 

after making false total=0 
after making false total=0 
after making false total=1 
inside 3rd if ,total= 1 
true false false 
true true false 
false true false 

inside 1st if ,total= 0 
inside 2nd if ,total= 1 
true false false 
true true false 
true true false 

after making false total=0 
after making false total=1 
inside 4th if ,total= 2 
true true false 
true true false 
false false false 

inside 1st if ,total= 0 
true true true 
true true false 
false false false 

inside 3rd if ,total= 0 
true true true 
true true true 
false false false 

inside 3rd if ,total= 0 
after making false total=1 
after making false total=1 
after making false total=1 
after making false total=3 
inside 3rd if ,total= 3 
true false false 
true false false 
true false false 

inside 1st if ,total= 0 
true false false 
true false false 
true true false 

inside 1st if ,total= 0 
inside 4th if ,total= 1 
true false false 
true true false 
true true false 

inside 1st if ,total= 0 
true false false 
true true true 
true true false 

inside 3rd if ,total= 0 
inside 4th if ,total= 1 
true false true 
true true true 
true true false 

inside 2nd if ,total= 0 
true true true 
true true true 
true true false 

after making false total=0 
after making false total=0 
after making false total=1 
inside 4th if ,total= 1 
true true false 
true true false 
true true false 

inside 1st if ,total= 0 
true true true 
true true false 
true true false 

inside 3rd if ,total= 0 
true true true 
true true true 
true true false 

inside 3rd if ,total= 0 
after making false total=1 
after making false total=1 
after making false total=1 
after making false total=2 
after making false total=3 
after making false total=3 
after making false total=6 
after making false total=12 
12 

Я недавно узнал о возвратах, и я пытаюсь понять этот код, как возвраты работают, но я не понимаю, что происходит после того, как мы нашли первый путь, как в программа знает, что нужно вернуться и сделать некоторые из ИСТИННЫХ ЛОЖНО:

inside 1st if ,total= 0 
after making false total=1 
after making false total=1 
after making false total=1 
inside 3rd if ,total= 1 
true true true 
false true true 
false true false 

Объяснение было бы действительно оценено, чтобы помочь мне понять.

Answer 1

Вышеупомянутый код на самом деле не отступает, а рекурсивный алгоритм поиска. Он рекурсивно просматривает вашу сетку, перемещаясь по глубине - сначала, влево, вправо, вниз, вверх, в этом порядке.

Он знаменует собой поле с истинной, когда она движется над ним, и помечает его с ложной когда он исчерпал все возможности в этой позиции (для текущих посещенных полей). Он отмечает поля, потому что он не пересматривает поле дважды, поэтому он ищет пути, которые посещают каждое поле не чаще одного раза.

Обратите внимание, что он снова оценивает поле для каждого пути, ведущего к этому полю.