为什么这个递归工作？有人能告诉我为什么这个代码有效吗？

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，这意味着这些变量的值将在调用堆栈中的该方法的所有调用之间共享。