爲什麼這個遞歸工作？有人能告訴我爲什麼這個代碼有效嗎？

Question

我被這個方法弄得暈頭轉向，我從http://visualbasic.about.com/b/2007/06/06/permutations-recursion-and-traversing-a-binary-tree.htm修改過。我在VB.net中重寫了它，儘管似乎需要大量的循環才能完成任何工作，但它很好用。

這種方法需要一個單詞，並返回該單詞中所有字母的變體，沿着它只顯示出現在字典中的單詞的方式，但那不是問題。

一旦它已經通過單詞中的字母，例如abcd，通過a，ab，abc等循環，它就會到達end子節點。

在那裏，我希望它停下來。但事實並非如此，這是我感到困惑的一點。它回到遞歸調用，並再次運行代碼從那裏到end sub，多次。如果有什麼，我會期望它回到sub的頂部，這本身會很奇怪，但是在遞歸調用之後不會回來。它沒有循環整個小組，並且看起來像是從那裏開始的。

SUBSECTION OF CODE 

    PermutationOfLetters() 
       ' Mark this item free again - start again 
       IsItemUsed(i) = False 

       ' Restore the current Perm 
       permutationString = PermWord 
      End If 
     Next 
      BGworker.ReportProgress(LoopCounter) 
     End Sub 

它需要做到這一點，以獲得分支工作，但我不明白是什麼讓它做到這一點？ 任何人都可以啓發我嗎？這很難解釋「巫毒在這裏發生」。

我剛剛注意到與原始代碼鏈接上的另一張海報問了同樣的問題。 :-)

所有代碼

Private Sub PermutationOfLetters() 
    'Just a counter to see how many time the Sub loops 
    Static RecursionCounter As ULong = 0 
    ' lbxWords.Items.Add("recursion " & RecursionCounter) 
    RecursionCounter += 1 

    'Just a counter to count how many loops in the For statement 
    Static LoopCounter As ULong = 0 


    'chop up the word into a character array w,o,r,d,s 
    Static WordIntoletters As Char() = myDictionary.SelectedWord.ToCharArray() 


    Static permutationString As String 

    ' gives a true /false for each letter as it passes through set false to start - Boolean Array 
    Static IsItemUsed(myDictionary.SelectedWord.Length - 1) As Boolean 

    Dim PermWord As String = permutationString ' Save the current Perm for each value currently available 

    'count through each letter and operate on those that are false 
    For i = 0 To myDictionary.SelectedWord.Length - 1 
     LoopCounter += 1 

     'when it finds a false then run the loop 
     If IsItemUsed(i) = False Then 
      'add another letter to the word 
      permutationString += WordIntoletters(i) 


      If FoundWordsDictionary.ContainsKey(permutationString) = False Then 

      End If 

      'if words are in the dictionary output real words and are not already saved 
      If myDictionary.WordDictionary.ContainsKey(permutationString) = True AndAlso FoundWordsDictionary.ContainsKey(permutationString) = False Then 
       ' lbxWords.Items.Add(i & " " & permutationString) 
       'pass the words through to the sorted dict for easy output 

       FoundWordsDictionary.Add(permutationString, permutationString) 
       ' lbxWords.Items.Add(permutationString) 
      End If 

      ' Mark this item unavailable - finished with a true 
      IsItemUsed(i) = True 'so don't come back to that letter 

      PermutationOfLetters() 
      ' Mark this item free again - start again 
      IsItemUsed(i) = False 

      ' Restore the current Perm 
      permutationString = PermWord 
     End If 
    Next 
     BGworker.ReportProgress(LoopCounter) 
    End Sub 

Answer 1

你似乎被什麼遞歸方法相混淆。當你遞歸地調用一個方法時，這意味着一個方法調用它自己。這樣做的時候，就像它調用不同的方法一樣。例如：

Public Sub Method1() 
    Console.WriteLine("Begin 1") 
    Method2() 
    Console.WriteLine("End 1") 
End Sub 

Public Sub Method2() 
    Console.WriteLine("2") 
End Sub 

希望這將是毫不奇怪，當你在上面的例子中調用Method1，將輸出以下行：

開始1 末1

從執行Method2回來時，它會繼續到下一行（Console.WriteLine("End 1")）。你當然不希望執行跳回到Method1的頂部。

遞歸以同樣的方式工作，但是在調用堆棧中不是使用兩種不同的方法，而是在調用堆棧中重複多次使用相同的方法。調用堆棧上方法的每個「實例」維護它自己的執行位置（這就是爲什麼它被稱爲堆棧）。方法當前調用的狀態保存在堆棧中，而下一次調用該方法的方法將添加到堆棧頂部。一旦完成執行內部方法調用，堆棧就會退回到前一個方法，該方法會從中斷的地方開始。

對該方法的每個調用也都有其自己的局部變量值的獨立副本。儘管在這種情況下，它將許多局部變量定義爲Static，這意味着這些變量的值將在調用堆棧中的該方法的所有調用之間共享。