C＃遞歸函數棧共享變量無處

Question

我試圖讓，使用回溯在迷宮找到哈密爾頓路徑的程序。它應該返回數字編碼的迷宮路徑。問題是當一個堆棧回退時，其中一個變量（這是迷宮的表示）從調用繼承，而其他變量（即使它們被聲明爲相同的方式）不（這是好的）。我嘗試了幾個解決方法，包括通過製作一個單獨的類來實例化，並且包含調試消息。這裏的代碼有一些意見可以幫助。

using System; 


namespace ConsoleApplication1 
{ 
    //I made a separate class for the function 
    class btr 
    { 
     public short[,] mz = new short[,] { };//tried to pull the variable out of the function, no success 
     public void bt(int i, int j, int l) 
     { 
      bool ok; 
      ok = true; 
      Console.WriteLine("in" + '\n' + Program.print(mz, l) + 'i' + i + 'j' + j + '\n'); //debug message for entering 
      if (i > 0 && mz[i - 1, j] == 0) 
      { 
       ok = false; 
       mz[i, j] = 1; // 1 aka go up 
       var x = new btr { }; 
       //my attempt to avoid the problem by instantiating the function, no success... 
       x.mz = mz; 
       x.bt(i - 1, j, l); 
       //When this function exits the mz variable is copied to this one. Same for all the ifs below 
      } 
      if (j > 0 && mz[i, j - 1] == 0) 
      { 
       ok = false; 
       mz[i, j] = 2; //2 aka go left 
       var x = new btr { }; 
       x.mz = mz; 
       x.bt(i, j - 1, l); 
      } 
      if (i < l && mz[i + 1, j] == 0) 
      { 
       ok = false; 
       mz[i, j] = 3;//3 aka go down 
       var x = new btr { }; 
       x.mz = mz; 
       x.bt(i + 1, j, l); 
      } 
      if (j < l && mz[i, j + 1] == 0) 
      { 
       ok = false; 
       mz[i, j] = 4;//4 aka go right 
       var x = new btr { }; 
       x.mz = mz; 
       x.bt(i, j + 1, l); 
      } 
      Console.WriteLine("out" + '\n' + Program.print(mz, l) + 'i' + i + 'j' + j + '\n'); //debug message for exiting 
      if (ok) //this is for printing the solution when it is found 
      { 
       mz[i, j] = 8;// 8 aka the end 
       foreach (int x in mz) 
       { 
        if (x == 0) { ok = false; break; } 
       } 
       if (ok) 
        Console.WriteLine("result" + '\n' + Program.print(mz, l)); 
      } 
     } 
    } 
    class Program 
    {//this is just for preparing the first call 

    static short[,] test = new short[2, 2] { { 0, 0}, { 0, 0} }; 

    static void Main(string[] args) 
    { 
     var x= new btr { }; 
     x.mz = test; 
     x.bt(0,0,1); 
    } 
    public static string print(short[,] vr,int l)//casts my array into a string that can be printed 
    { 
     string s = ""; 
     for (int i = 0; i <= l; i++) 
     { 
      for (int j = 0; j <= l; j++) 
      { 
       s += vr[i,j]; 
      } 
      s += '\n'; 
     } 
     return s; 
    } 
} 

}

我給作爲測試一個2x2迷宮沒有任何障礙（由試驗爲代表宣佈所有0），它應該輸出2個解決方案中，僅輸出一個和該溶液被「注入」到堆棧。這裏的輸出：

in 
00 
00 
i0j0 

in 
30 
00 
i1j0 

in 
30 
40 
i1j1 

in 
30 
41 
i0j1 

out 
30 
41 
i0j1 

result 
38 
41 

out 
38 
41 
i1j1 

out 
38 
41 
i1j0 

out 
38 
41 
i0j0 

當函數退出迷宮，你可以看到保持38 41，而不是逐漸回落至00 00，以便更多的解決方案可以計算出來。我和j不受影響。

Answer 1

我同意不變性是一種有用的技術與遞歸打交道時，特別是在需要反向跟蹤。也就是說，它在處理數組時可能會產生不必要的開銷，特別是在數組很大時。

在您的情況，因爲你知道你正在修改什麼，數組的元素，你讓你的遞歸調用之前，你可以簡單地遞歸調用返回後重置價值。從某種意義上說，你是趁着調用堆棧在這種情況下保持狀態—，在i和修改—數組元素的j並使用遞歸調用後恢復狀態。

這將是這個樣子：

public void bt(int i, int j, int l) 
{ 
    bool ok; 
    ok = true; 
    Console.WriteLine("in" + '\n' + Program.print(mz, l) + 'i' + i + 'j' + j + '\n'); //debug message for entering 
    if (i > 0 && mz[i - 1, j] == 0) 
    { 
     ok = false; 
     mz[i, j] = 1; // 1 aka go up 
     bt(i - 1, j, l); 
     mz[i, j] = 0; 
     //When this function exits the mz variable is copied to this one. Same for all the ifs below 
    } 
    if (j > 0 && mz[i, j - 1] == 0) 
    { 
     ok = false; 
     mz[i, j] = 2; //2 aka go left 
     bt(i, j - 1, l); 
     mz[i, j] = 0; 
    } 
    if (i < l && mz[i + 1, j] == 0) 
    { 
     ok = false; 
     mz[i, j] = 3;//3 aka go down 
     bt(i + 1, j, l); 
     mz[i, j] = 0; 
    } 
    if (j < l && mz[i, j + 1] == 0) 
    { 
     ok = false; 
     mz[i, j] = 4;//4 aka go right 
     bt(i, j + 1, l); 
     mz[i, j] = 0; 
    } 
    Console.WriteLine("out" + '\n' + Program.print(mz, l) + 'i' + i + 'j' + j + '\n'); //debug message for exiting 
    if (ok) //this is for printing the solution when it is found 
    { 
     mz[i, j] = 8;// 8 aka the end 
     foreach (int x in mz) 
     { 
      if (x == 0) { ok = false; break; } 
     } 
     if (ok) 
      Console.WriteLine("result" + '\n' + Program.print(mz, l)); 
    } 
} 

注意mz[i, j] = 0;每次通話後。

如果你願意，你甚至可以把mz變回方法的參數列表。你只處理數組的單個實例，所以將它作爲類字段或方法參數保存並不重要。