CODEWITHSUNDEEP
vb.netrecursion
netchicken
netchicken

Reputation: 485

Why does this recursion work? Can someone tell me why this code works?

I am flummoxed by this method that I modified from http://visualbasic.about.com/b/2007/06/06/permutations-recursion-and-traversing-a-binary-tree.htm. I rewrote it in VB.net, and it woks well although does seem to take a ton of loops to get anything done.

This method takes in a word, and returns all the variations of the letters in that word, along the way it shows only the words that appear in the dictionary, but thats not the issue.

Once it has been through the letters in the word such as abcd, cycling through a, ab, abc, etc it reaches the end sub.

There I would expect it to stop. But it doesn't, and here is the bit that I am confused about. It comes back to the recursive call and runs the code from there to the end sub again, multiple times. If anything I would expect it to go back to the top of the sub, which would be odd in itself, but not back to after the recursion call. Its not looping through the whole sub and looking like its starting there either.

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

It needs to do that to get the branching working but I can't see what makes it do that? Can anyone enlighten me? It makes it hard to explain that "Voodoo happens here".

I just noticed another poster on the link with the original code asked the same question. :-)

ALL CODE

 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

Upvotes: 1

Views: 79

Answers (1)

Steven Doggart
Steven Doggart

Reputation: 43743

You seemed to be confused by what recursion means. When you call a method recursively, that means that a method calls itself. In so doing, it acts just like it does when it calls a different method. For instance:

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

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

Hopefully it will come as no surprise that when you call Method1 in the example above, it will output the following lines:

Begin 1
2
End 1

When it comes back from executing Method2, it continues to the next line (Console.WriteLine("End 1")). You certainly wouldn't expect execution to jump back to the top of Method1 at that point.

Recursion works the same way, but instead of two different methods being in the call stack, you end up with the same method repeated multiple times in the call stack. Each "instance" of the method on the call stack maintains it's own execution position (that's why it's called a stack). The state of the current call to the method is maintained in the stack while the next call to the method is added on top of it on the stack. Once it's done executing the inner method call, the stack unwinds back to the previous method which picks up where it left off.

Each call to the method has its own independent copy of its local variable values too. Although, in this case, it defines many of its local variables as Static which means that the values of those variables will be shared across all calls to that method in the call stack.

Upvotes: 2

Related Questions