Visual Basic 2010 Recursie Procedures en Functies

home links
visual basic 2010 broncode voorbeelden

8.14. Recursie

Dit artikel is gepubliceerd op zondag 31 juli 2011 op vbvoorbeelden, bezoek de website voor een recente versie van dit artikel of andere artikels.

8.14.1. Faculteitsberekening

Om de faculteit te berekenen van een bepaald getal zouden we onderstaand programma kunnen schrijven.

Enkele voorbeelden van faculteitsberekening :

- de faculteit van 5 : 5! = 5 x 4 x 3 x 2 x 1  = 120
- de faculteit van 4 : 4! =     4 x 3 x 2 x 1  = 24
- de faculteit van 3 : 3! =         3 x 2 x 1  = 6
- de faculteit van 2 : 2! =             2 x 1  = 2
- de faculteit van 1 : 1! =                 1  = 1

Uitzonderlijk geval :

- de faculteit van 0 : 0! = 1

Visual Basic 2010 Broncode

Module Example1
    Sub Main()
        Console.WriteLine(GetFaculty(0))
        Console.WriteLine(GetFaculty(1))
        Console.WriteLine(GetFaculty(2))
        Console.WriteLine(GetFaculty(3))
        Console.WriteLine(GetFaculty(4))
        Console.WriteLine(GetFaculty(5))
        '
        Console.ReadLine()
    End Sub
    Function GetFaculty(ByVal value As Integer) As Integer
        GetFaculty = 1
        For factor As Integer = value To 2 Step -1
            GetFaculty *= factor
        Next
    End Function
End Module

Download Visual Basic 2010 Broncode Download Visual C# Sourcecode

Console Application Output

Aan de hand van een iteratie structuur kunnen we de faculteit van een bepaald getal bepalen door alle gehele getallen kleiner en gelijk aan dat bepaalde getal en groter dan één ( of groter dan nul ) met elkaar te gaan vermenigvuldigen.

Een alternatieve oplossing is ook mogelijk, namelijk gebruik maken van "recursie".

Recursie wordt technisch gezien bekomen door een method in bepaalde situaties zichzelf te laten aanroepen.

Recursie is bruikbaar wanneer je een probleem kan oplossen door eerst een kleiner deelprobleem op te lossen.

Het voordeel van recursie is dat je hiermee vaak de code korter en eleganter kan maken.

Werkwijze om recursie te gebruiken :

1. bedenk hoe het probleem vereenvoudigd kan worden tot een kleiner analoog deelprobleem
2. zoek naar het/de trivia(a)l(e) geval(len) ( situatie(s) waarin er geen vereenvoudiging meer kan of nodig is door het op te lossen met een kleiner analoog deelprobleem )

Laten we de werkwijze uitdiepen door terug te keren naar ons voorbeeld van faculteitsberekening.

Het oorspronkelijke probleem is dat we de faculteit van een bepaald getal moeten kunnen bepalen.

We gaan na of we dit met recursie kunnen oplossen door te kijken of we het probleem kunnen vereenvoudigen door eerst een kleiner ( analoog ) deelprobleem op te lossen.

5! = 5 x 4 x 3 x 2 x 1 = 120
4! = 4 x 3 x 2 x 1 = 24

Als we een goed kijken naar de voorbeelden dan zie je dat het bepalen van de faculteit van 5 en 4 grotendeels gelijk is, maar er bij het bepalen van de faculteit van 5 enkel nog een vermenigvuldiging met 5 zelf bovenop komt.

We kunnen de faculteit van 5 dus bepalen, door eerst de faculteit van 4 te bepalen en vervolgens met 5 te vermenigvuldigen :

5! = 5 x 4!

Dezelfde redenering gaat ook op voor een aantal andere getallen :

4! = 4 x 3! = 4 x 6 = 24
3! = 3 x 2! = 3 x 2 = 6
2! = 2 x 1! = 2 x 1 = 2
1! = 1 x 0! = 1 x 1 = 1

In het algemeen kun je dus stellen dat :

n! = n x (n-1)!

Nogmaals : het probleem van de faculteit van een bepaald getal ( bv 5 ) te bepalen kan dus vereenvoudigd worden door eerst een kleiner analoog deelprobleem op te lossen, namelijk de faculteit van dat bepaald getal verminderd met 1 te bepalen ( bv 4 ).

De redenering gaat niet meer op voor 0, want de faculteit van 0 is gewoon simpelweg 1. Dit is dus het triviaal geval, gezien we hier het probleem van de faculteit te bepalen van 0, niet meer kunnen vereenvoudigen door eerst de faculteit van 0 verminderd met 1 te bepalen.

Het bepalen van de faculteit van dat bepaald getal verminderd met 1 is een analoog deelprobleem omdat het ook het bepalen van de faculteit van een getal is.

Het bepalen van de faculteit van dat bepaald getal verminderd met 1 is een kleiner deelprobleem omdat het dichter aanleunt bij het triviaal geval. "Kleiner" hoef je dus niet letterlijk te nemen, maar met "kleiner deelprobleem" bedoeld men dus een deelprobleem die dichter aanleunt bij het/de trivia(a)l(e) geval(len). Het bepalen van de faculteit van 4 is dus een kleiner deelprobleem voor het bepalen van de faculteit van 5, omdat 4 dichter aanleunt bij 0.

De recursieve oplossing zou er dus als volgt kunnen uitzien :

Visual Basic 2010 Broncode

Module Example2
    Sub Main()
        Console.WriteLine(GetFaculty(0))
        Console.WriteLine(GetFaculty(1))
        Console.WriteLine(GetFaculty(2))
        Console.WriteLine(GetFaculty(3))
        Console.WriteLine(GetFaculty(4))
        Console.WriteLine(GetFaculty(5))
        '
        Console.ReadLine()
    End Sub
    Function GetFaculty(ByVal value As Integer) As Integer
        If value = 0 Then
            GetFaculty = 1
        Else
            GetFaculty = value * GetFaculty(value - 1)
        End If
    End Function
End Module

Download Visual Basic 2010 Broncode Download Visual C# Sourcecode

Console Application Output

Ga altijd na in de recursieve implementatie of de uitvoeringsinstantie zich in een triviaal geval bevindt ( dus hier controleren : value = 0 ), om in dat geval de triviale waarde op te leveren ( bij functies ) of de triviale actie uit te voeren ( bij procedures ) ( dus hier triviale terugkeerwaarde 1 instellen : GetFaculty = 1 ). Bevindt men zich niet in het triviaal geval, dan kan recursief gewerkt worden, door de terugkeerwaarde te baseren op de terugkeerwaarde in het analoog "kleiner" geval ( bij functies ) of door de actie uit breiden met de actie voor het analoog "kleiner" geval ( bij procedures ).

Zoals reeds gesteld werd kan men dus zowel recursieve functies als procedures creëren.

Bovenstaande recursieve oplossing is niet korter in aantal regels dan de niet recursieve variant, met andere probleem-stellingen zal dit echter wel vaak het geval zijn.

Visual Studio : In Visual Studio kan men in het Call Stack-toolvenster goed constateren welke uitvoeringsinstantie welke andere uitvoeringsinstantie aanroept.

boven boven

8.14.2. Bepalen van de Grootste Gemene Deler

De "grootste gemene deler" van 2 getallen x en y, met |x| >= |y| is :

1. |x| als y = 0
2. |y| als |x| mod |y| = 0
3. = grootste gemene deler van |y| en ( |x| mod |y| ) ( als niet 1. of 2. )

Visual Basic 2010 Broncode

Module Example3
    Sub Main()
        Console.WriteLine(GetCommonDivisor(3, 9))
        Console.WriteLine(GetCommonDivisor(3, -9))
        Console.WriteLine(GetCommonDivisor(8, 3))
        Console.WriteLine(GetCommonDivisor(-3, -8))                        ' (1)
        Console.WriteLine(GetCommonDivisor(6, 0))
        Console.WriteLine(GetCommonDivisor(0, 6))
        Console.WriteLine(GetCommonDivisor(8, 12))
        Console.WriteLine(GetCommonDivisor(9, 9))
        '
        Console.ReadLine()
    End Sub
    Function GetCommonDivisor(ByVal value1 As Integer, _
                              ByVal value2 As Integer) As Integer
        If value1 < 0 Then
            GetCommonDivisor = GetCommonDivisor( value1, value2)
        ElseIf value2 < 0 Then
            GetCommonDivisor = GetCommonDivisor(value1,  value2)
        ElseIf value1 < value2 Then
            GetCommonDivisor = GetCommonDivisor(value2, value1)
        ElseIf value2 = 0 Then
            GetCommonDivisor = value1
        Else
            GetCommonDivisor = GetCommonDivisor(value2, value1 Mod value2)
        End If
    End Function
End Module

Download Visual Basic 2010 Broncode Download Visual C# Sourcecode

Console Application Output

Als je de uitvoeringsinstanties bekijkt voor de aanroep op regel (1) met bovenstaande implementatie, dan zie je hoe :

GetCommonDivisor(-3, -8)
wordt gebaseerd op :
GetCommonDivisor(3, -8)
wordt gebaseerd op :
GetCommonDivisor(3, 8)
wordt gebaseerd op :
GetCommonDivisor(8, 3)
wordt gebaseerd op :
GetCommonDivisor(3, 8 Mod 3) ( of dus GetCommonDivisor(3, 2) )
wordt gebaseerd op :
GetCommonDivisor(2, 3 Mod 2) ( of dus GetCommonDivisor(2, 1) )
wordt gebaseerd op :
GetCommonDivisor(1, 2 Mod 1) ( of dus GetCommonDivisor(1, 0) )
wat resulteert in :
1

Deze keer wordt het resultaat van 1 uitvoeringsinstantie rechtstreeks gebaseerd op het resultaat van de aangeroepen uitvoeringsinstantie.

boven boven

8.14.3. Machtsverheffing

Ook machtsverheffing kan recursief geïmplementeerd worden.

Als triviaal geval zou je exponent 0 kunnen nemen, want eender welk getal tot de 0de macht is 1.

Bij een positieve exponent kan je stellen dat :

X ^ Y = X * ( X ^ ( Y - 1 ) )

Bij een negatieve exponent kan je stellen dat :

X ^ Y = 1 / ( X ^ -Y )

Visual Basic 2010 Broncode

Module Example4
    Sub Main()
        Console.WriteLine(GetPower(2, 3))
        Console.WriteLine(GetPower(2, 2))
        Console.WriteLine(GetPower(2, 1))
        Console.WriteLine(GetPower(2, 0))
        Console.WriteLine(GetPower(2, -1))
        Console.WriteLine(GetPower(2, -2))
        Console.WriteLine(GetPower(2, -3))
        '
        Console.ReadLine()
    End Sub
    '
    Function GetPower(ByVal base As Integer, _
                      ByVal exponent As Integer) As Integer
        If exponent = 0 Then
            GetPower = 1
        ElseIf exponent > 0 Then
            GetPower = base * GetPower(base, exponent - 1)
        ElseIf exponent < 0 Then
            GetPower = 1 / GetPower(base, -exponent)
        End If
    End Function
End Module

Download Visual Basic 2010 Broncode Download Visual C# Sourcecode

Console Application Output

boven boven

8.14.4. Fibonacci

De "Fibonacci"-reeks is een reeks van getallen die begint met 2 maal het getal 1, elk daarop volgend getal is gelijk aan de som van de vorige 2 getallen uit de reeks.

Fibonaccireeks : 1 1 2 3 5 8 13 21 34 55 ...

Als we een functie zouden willen schrijven voor het bepalen van een bepaald getal - gebaseerd op de rang - uit deze reeks ( Function GetFibo(ByVal ordinal As Integer) As Integer ) zouden we recursief te werk kunnen gaan.

Om het tiende fibonaccigetal te bepalen, kunnen we eerst 2 analoge kleinere deelproblemen oplossen, namelijk het bepalen van het achtste ( 21 ) en het negende ( 34 ) fibonaccigetal, om deze vervolgens op te tellen en tot het tiende fibonaccigetal te komen ( 55 ).

Triviaal is hier het opvragen van het eerste of tweede fibonaccigetal, deze kunnen niet bepaald worden door eerst een kleiner analoog deelprobleem op te lossen, maar deze zijn simpelweg 1.

Visual Basic 2010 Broncode

Module Example5
    Sub Main()
        Console.WriteLine(GetFibo(1))
        Console.WriteLine(GetFibo(2))
        Console.WriteLine(GetFibo(3))
        Console.WriteLine(GetFibo(4))
        Console.WriteLine(GetFibo(5))
        Console.WriteLine(GetFibo(6))
        Console.WriteLine(GetFibo(7))
        Console.WriteLine(GetFibo(8))
        Console.WriteLine(GetFibo(9))
        Console.WriteLine(GetFibo(10))
        '
        Console.ReadLine()
    End Sub
    Function GetFibo(ByVal ordinal As Integer) As Integer
        If ordinal = 1 OrElse ordinal = 2 Then
            GetFibo = 1
        ElseIf ordinal > 2 Then
            GetFibo = GetFibo(ordinal - 1) + GetFibo(ordinal - 2)
        End If
    End Function
End Module

Download Visual Basic 2010 Broncode Download Visual C# Sourcecode

Console Application Output

Efficiënt is echter anders, een te groot aantal uitvoeringsinstanties moet worden uitgevoerd vooraleer het uiteindelijke resultaat kan bepaald worden.

Voor het recursief bepalen van het eerste of tweede fibonaccigetal moet slechts 1 uitvoeringsinstantie worden uitgevoerd, voor het derde fibonaccigetal zijn dit reeds 3 uitvoeringsinstanties, voor het vierde fibonaccigetal zijn dit er 5, voor het vijfde fibonaccigetal zijn dit er 9, voor het zesde fibonaccigetal zijn dit er 15, voor het zevende fibonaccigetal zijn dit er 25, voor het achtste fibonaccigetal zijn dit er 41, voor het negende fibonaccigetal zijn dit er 67, voor het tiende fibonaccigetal zijn dit er 109, ... .

Dat wil dus bijvoorbeeld zeggen dat voor het bepalen van het tiende fibonaccigetal er 109 Integers in het geheugen worden gereserveerd.

Conclusie is dat niet alles wat recursief op te lossen valt ook perse zo moet worden geïmplementeerd, houd steeds ( de groei van ) het aantal uitvoeringsinstanties in het oog.

Een niet-recursieve oplossing valt hier te verkiezen :

Visual Basic 2010 Broncode

Module Example6
    Sub Main()
        Console.WriteLine(GetFibo(1))
        Console.WriteLine(GetFibo(2))
        Console.WriteLine(GetFibo(3))
        Console.WriteLine(GetFibo(4))
        Console.WriteLine(GetFibo(5))
        Console.WriteLine(GetFibo(6))
        Console.WriteLine(GetFibo(7))
        Console.WriteLine(GetFibo(8))
        Console.WriteLine(GetFibo(9))
        Console.WriteLine(GetFibo(10))
        '
        Console.ReadLine()
    End Sub
    Function GetFibo(ByVal ordinal As Byte) As Integer
        GetFibo = 1
        If ordinal > 2 Then
            Dim fibo1 As Short = 1
            Dim fibo2 As Short = 1
            Dim count As Byte = 2
            Do Until count = ordinal
                Dim backup As Integer = fibo2
                fibo2 += fibo1
                fibo1 = backup
                count += 1
            Loop
            GetFibo = fibo2
        End If
    End Function
End Module

Download Visual Basic 2010 Broncode Download Visual C# Sourcecode

Console Application Output

boven boven

8.14.5. Quick Sort

Een van de meest performante "in-place" sorteermethoden is de "Quick Sort", die het eenvoudigst recursief te implementeren is.

Deze methode bestaat erin steeds ( middelste ) "pivot" element te bepalen, en de overige tabelelementen op basis van hun verhouding ten aanzien van de "pivot" te gaan pivoteren rond die "pivot".

Veronderstel volgende ongesorteerde tabel :

indices : 0 1 2 3 4 5 6 7
waarden : 88 75 93 81 21 74 84 35

Bepaal een middelste element of middelste index : ( 0 + 7 ) \ 2 = 3.
81 is de "pivot" waarde ( element op index 3 ), deze "pivot" waarde plaatsen we aan de kant ( bijvoorbeeld achteraan de tabel door 81 en 35 van positie te wisselen ) :

indices :     0       1       2       3       4       5       6       7
waarden :     88      75      93      35      21      74      84      81
                                                                      pivot

We zoeken startende bij het begin van de tabel naar een waarde die groter is dan ( of gelijk aan ) de "pivot" waarde :

indices :     0       1       2       3       4       5       6       7
waarden :     88      75      93      35      21      74      84      81
              groter                                                  pivot

En startende bij het einde van de tabel naar een waarde die kleiner is ( of gelijk aan ) de "pivot" waarde :

indices :     0       1       2       3       4       5       6       7
waarden :     88      75      93      35      21      74      84      81
              groter                                  kleiner         pivot

Deze waarde wisselen we van positie ( pivoteren ) :

indices :     0       1       2       3       4       5       6       7
waarden :     74      75      93      35      21      88      84      81
                                                                      pivot

Startende bij de uit vorige stap bereikte posities zoeken we verder naar een kleinere en grotere waarde dan de "pivot" :

indices :     0       1       2       3       4       5       6       7
waarden :     74      75      93      35      21      88      84      81
                              groter          kleiner                 pivot

Opnieuw wisselen we de waarden van positie ( pivoteren ) :

indices :     0       1       2       3       4       5       6       7
waarden :     74      75      21      35      93      88      84      81
                                              *                       pivot

Bij het verder zoeken naar een grotere waarde dan de "pivot" komen we aan de positie waar het laatst een kleinere waarde dan de "pivot" werd gevonden ( index 4 ). Verder ( op hogere indices ) naar een grotere waarde dan de "pivot" zoeken heeft geen zin, gezien we daar enkel waarden gaan terugvinden die ten opzichte van de "pivot" reeds juist gepivoteerd zitten.

Met andere woorden : we weten dat voor index 4 elementen zitten die kleiner zijn of gelijk aan de "pivot" waarde en vanaf index 4 elementen zitten die groter zijn of gelijk aan de pivot waarde. De "pivot" kan nu terug op zijn juiste positie worden geplaatst ( index 4 ) :

indices : 0 1 2 3 4 5 6 7
waarden : 74 75 21 35 81 88 84 93

81 zit juist dus hebben we nog 2 ongesorteerde delen :

deel 1 :                                              deel 2 :
indices :     0       1       2       3               5       6       7
waarden :     74      75      21      35              88      84      93

Om deze ongesorteerde delen verder te sorteren kunnen we dezelfde werkwijze gebruiken, of dit dus als een analoog kleiner deelprobleem beschouwen.

Als het ongesorteerde deel minder groot is dan 3 elementen ( 0, 1 of 2 elementen ) kan/hoeft dezelfde werkwijze niet worden toegepast, en bevinden we ons dus in triviale gevallen :

Visual Basic 2010 Broncode

Module QuickSort
    Sub Main()
        Dim numbers As Integer() = {88, 75, 93, 81, 21, 74, 84, 35}
        PrintArray(numbers)
        '
        QuickSort(numbers, 0, 7)
        PrintArray(numbers)
        '
        Console.ReadLine()
    End Sub
    Sub PrintArray(ByVal values As Integer())
        For Each value As Integer In values
            Console.Write(value & " ")
        Next
        Console.WriteLine()
    End Sub
    Sub QuickSort(ByVal array As Integer(), _
                  ByVal lowerbound As Integer, ByVal upperbound As Integer)
        Dim count As Integer = upperbound - lowerbound + 1
        If count = 2 Then
            If array(lowerbound) > array(upperbound) Then
                Dim backup As Integer = array(lowerbound)
                array(lowerbound) = array(upperbound)
                array(upperbound) = backup
            End If
        ElseIf count > 2 Then
            Dim pivotIndex As Integer = (lowerbound + upperbound) \ 2
            Dim pivot As Integer = array(pivotIndex)
            '
            array(pivotIndex) = array(upperbound)
            array(upperbound) = pivot
            '
            Dim smallerIndex As Integer = lowerbound
            Dim biggerIndex As Integer = upperbound
            '
            Do While smallerIndex <> biggerIndex
                '
                Do While array(smallerIndex) <= pivot AndAlso _
                         smallerIndex < biggerIndex
                    smallerIndex += 1
                Loop
                '
                Do While array(biggerIndex) >= pivot AndAlso _
                         smallerIndex < biggerIndex
                    biggerIndex -= 1
                Loop
                '
                If smallerIndex <> biggerIndex Then
                    Dim backup As Integer = array(smallerIndex)
                    array(smallerIndex) = array(biggerIndex)
                    array(biggerIndex) = backup
                End If
            Loop
            '
            array(upperbound) = array(biggerIndex)
            array(biggerIndex) = pivot
            '
            QuickSort(array, lowerbound, biggerIndex - 1)
            QuickSort(array, smallerIndex + 1, upperbound)
        End If
    End Sub
End Module

Download Visual Basic 2010 Broncode Download Visual C# Sourcecode

Console Application Output

88 75 93 81 21 74 84 35
21 35 74 75 81 84 88 93

boven boven

8.14.6. Backtracking

Om sommige problemen op te lossen ( zoals het "N Dames Probleem" ) moet men tijdens het zoeken naar een oplossing terugkeren naar een vorige gevonden deeloplossing. Dit terugkeren wordt ook wel "backtracking" genoemd.

Visual Basic 2010 Broncode

Module NQueensProblem
    ' Problem :
    ' How to assign N queens to N positions on a N by N chessboard, so that no
    ' queen can attack any other queen on the board.
    '
    ' Configuration :
    Const N As Integer = 8
    '
    Dim chessBoard(N - 1, N - 1) As Boolean
    ' elements contain True if queen is assigned to according position
    '
    Sub Main()
        If CanSolve(N) Then
            Console.WriteLine("A solution is found :")
            DrawChessBoard()
        Else
            Console.WriteLine("No solution is found.")
        End If
        '
        Console.ReadLine()
    End Sub
    Sub DrawChessBoard()
        Console.Write("+")
        For col As Integer = 0 To N - 1
            Console.Write("---+")
        Next
        Console.WriteLine()
        For row As Integer = 0 To N - 1
            Console.Write("|")
            For col As Integer = 0 To N - 1
                If HasQueen(row, col) Then
                    Console.Write(" Q |")
                Else
                    Console.Write("   |")
                End If
            Next
            Console.WriteLine()
            Console.Write("+")
            For col As Integer = 0 To N - 1
                Console.Write("---+")
            Next
            Console.WriteLine()
        Next
        Console.WriteLine()
    End Sub
    Function CanSolve(ByVal queens As Integer) As Boolean
        If queens = 0 Then
            CanSolve = True
        Else
            Dim col As Integer = N - queens
            Dim rowToTry As Integer = 0
            Do
                If IsUnderAttack(rowToTry, col) Then
                    rowToTry += 1
                Else
                    PlaceQueen(rowToTry, col)
                    Console.WriteLine("Trying :")                          ' (*)
                    DrawChessBoard()                                       ' (*)
                    CanSolve = CanSolve(queens - 1)
                    If Not CanSolve Then
                        RemoveQueen(rowToTry, col)
                        Console.WriteLine("Backtracking to :")             ' (*)
                        DrawChessBoard()                                   ' (*)
                        rowToTry += 1
                    End If
                End If
            Loop Until CanSolve OrElse Not IsLegalPosition(rowToTry, col)
        End If
        ' (*) for debugging purposes
    End Function
    Function IsUnderAttack(ByVal row As Integer, ByVal col As Integer) As Boolean
        IsUnderAttack = IsUnderAttack(row, col, -1, -1) OrElse _
                        IsUnderAttack(row, col, +1, -1) OrElse _
                        IsUnderAttack(row, col, 0, -1)
    End Function
    Function IsUnderAttack(ByVal row As Integer, ByVal col As Integer, _
                           ByVal rowOffSet As Integer, ByVal colOffSet As Integer) As Boolean
        Do
            row += rowOffSet
            col += colOffSet
        Loop While IsLegalPosition(row, col) AndAlso Not HasQueen(row, col)
        IsUnderAttack = HasQueen(row, col)
    End Function
    Function HasQueen(ByVal row As Integer, ByVal col As Integer) As Boolean
        HasQueen = IsLegalPosition(row, col) AndAlso chessBoard(row, col)
    End Function
    Function IsLegalPosition(ByVal row As Integer, ByVal col As Integer) As Boolean
        IsLegalPosition = row >= 0 AndAlso row <= N - 1 AndAlso col >= 0 AndAlso col <= N - 1
    End Function
    Sub PlaceQueen(ByVal row As Integer, ByVal col As Integer)
        chessBoard(row, col) = True
    End Sub
    Sub RemoveQueen(ByVal row As Integer, ByVal col As Integer)
        chessBoard(row, col) = False
    End Sub
End Module

Download Visual Basic 2010 Broncode Download Visual C# Sourcecode

Voor N = 3 :

Console Application Output

Trying :
+---+---+---+
| Q |   |   |
+---+---+---+
|   |   |   |
+---+---+---+
|   |   |   |
+---+---+---+

Trying :
+---+---+---+
| Q |   |   |
+---+---+---+
|   |   |   |
+---+---+---+
|   | Q |   |
+---+---+---+

Backtracking to :
+---+---+---+
| Q |   |   |
+---+---+---+
|   |   |   |
+---+---+---+
|   |   |   |
+---+---+---+

Backtracking to :
+---+---+---+
|   |   |   |
+---+---+---+
|   |   |   |
+---+---+---+
|   |   |   |
+---+---+---+

Trying :
+---+---+---+
|   |   |   |
+---+---+---+
| Q |   |   |
+---+---+---+
|   |   |   |
+---+---+---+

Backtracking to :
+---+---+---+
|   |   |   |
+---+---+---+
|   |   |   |
+---+---+---+
|   |   |   |
+---+---+---+

Trying :
+---+---+---+
|   |   |   |
+---+---+---+
|   |   |   |
+---+---+---+
| Q |   |   |
+---+---+---+

Trying :
+---+---+---+
|   | Q |   |
+---+---+---+
|   |   |   |
+---+---+---+
| Q |   |   |
+---+---+---+

Backtracking to :
+---+---+---+
|   |   |   |
+---+---+---+
|   |   |   |
+---+---+---+
| Q |   |   |
+---+---+---+

Backtracking to :
+---+---+---+
|   |   |   |
+---+---+---+
|   |   |   |
+---+---+---+
|   |   |   |
+---+---+---+

No solution is found.

Voor N = 4 :

Console Application Output

Trying :
+---+---+---+---+
| Q |   |   |   |
+---+---+---+---+
|   |   |   |   |
+---+---+---+---+
|   |   |   |   |
+---+---+---+---+
|   |   |   |   |
+---+---+---+---+

Trying :
+---+---+---+---+
| Q |   |   |   |
+---+---+---+---+
|   |   |   |   |
+---+---+---+---+
|   | Q |   |   |
+---+---+---+---+
|   |   |   |   |
+---+---+---+---+

Backtracking to :
+---+---+---+---+
| Q |   |   |   |
+---+---+---+---+
|   |   |   |   |
+---+---+---+---+
|   |   |   |   |
+---+---+---+---+
|   |   |   |   |
+---+---+---+---+

Trying :
+---+---+---+---+
| Q |   |   |   |
+---+---+---+---+
|   |   |   |   |
+---+---+---+---+
|   |   |   |   |
+---+---+---+---+
|   | Q |   |   |
+---+---+---+---+

Trying :
+---+---+---+---+
| Q |   |   |   |
+---+---+---+---+
|   |   | Q |   |
+---+---+---+---+
|   |   |   |   |
+---+---+---+---+
|   | Q |   |   |
+---+---+---+---+

Backtracking to :
+---+---+---+---+
| Q |   |   |   |
+---+---+---+---+
|   |   |   |   |
+---+---+---+---+
|   |   |   |   |
+---+---+---+---+
|   | Q |   |   |
+---+---+---+---+

Backtracking to :
+---+---+---+---+
| Q |   |   |   |
+---+---+---+---+
|   |   |   |   |
+---+---+---+---+
|   |   |   |   |
+---+---+---+---+
|   |   |   |   |
+---+---+---+---+

Backtracking to :
+---+---+---+---+
|   |   |   |   |
+---+---+---+---+
|   |   |   |   |
+---+---+---+---+
|   |   |   |   |
+---+---+---+---+
|   |   |   |   |
+---+---+---+---+

Trying :
+---+---+---+---+
|   |   |   |   |
+---+---+---+---+
| Q |   |   |   |
+---+---+---+---+
|   |   |   |   |
+---+---+---+---+
|   |   |   |   |
+---+---+---+---+

Trying :
+---+---+---+---+
|   |   |   |   |
+---+---+---+---+
| Q |   |   |   |
+---+---+---+---+
|   |   |   |   |
+---+---+---+---+
|   | Q |   |   |
+---+---+---+---+

Trying :
+---+---+---+---+
|   |   | Q |   |
+---+---+---+---+
| Q |   |   |   |
+---+---+---+---+
|   |   |   |   |
+---+---+---+---+
|   | Q |   |   |
+---+---+---+---+

Trying :
+---+---+---+---+
|   |   | Q |   |
+---+---+---+---+
| Q |   |   |   |
+---+---+---+---+
|   |   |   | Q |
+---+---+---+---+
|   | Q |   |   |
+---+---+---+---+

A solution is found :
+---+---+---+---+
|   |   | Q |   |
+---+---+---+---+
| Q |   |   |   |
+---+---+---+---+
|   |   |   | Q |
+---+---+---+---+
|   | Q |   |   |
+---+---+---+---+

boven boven

8.14.7. Oefeningen

Opgave :

Breid onderstaande programmacode uit met de recursieve functie GetRowToZero.

Visual Basic 2010 Broncode

Module Exercise1Task
    Sub Main()
        'Console.WriteLine(GetRowToZero(5))
        'Console.WriteLine(GetRowToZero(-3))
        'Console.WriteLine(GetRowToZero(0))
        '
        Console.ReadLine()
    End Sub
End Module

Download Visual Basic 2010 Broncode Download Visual C# Sourcecode

Console Application Output

5 4 3 2 1 0
-3 -2 -1 0
0

Oplossing :

Visual Basic 2010 Broncode

Module Exercise1Solution
    Sub Main()
        Console.WriteLine(GetRowToZero(5))
        Console.WriteLine(GetRowToZero(-3))
        Console.WriteLine(GetRowToZero(0))
        '
        Console.ReadLine()
    End Sub
    Function GetRowToZero(ByVal value As Integer) As String
        If value = 0 Then
            GetRowToZero = 0
        ElseIf value < 0 Then
            GetRowToZero = value & " " & GetRowToZero(value + 1)
        Else 'If value > 0 Then
            GetRowToZero = value & " " & GetRowToZero(value - 1)
        End If
    End Function
End Module

Download Visual Basic 2010 Broncode Download Visual C# Sourcecode

Opgave :

Breid onderstaande programmacode uit met de recursieve functie GetRow.

Visual Basic 2010 Broncode

Module Exercise2Task
    Sub Main()
        'Console.WriteLine(GetRow(2, -3))
        'Console.WriteLine(GetRow(0, 2))
        'Console.WriteLine(GetRow(-3, -4))
        '
        Console.ReadLine()
    End Sub
End Module

Download Visual Basic 2010 Broncode Download Visual C# Sourcecode

Console Application Output

-2 -1 0 1
1

Oplossing :

Visual Basic 2010 Broncode

Module Exercise2Solution
    Sub Main()
        Console.WriteLine(GetRow(2, -3))
        Console.WriteLine(GetRow(0, 2))
        Console.WriteLine(GetRow(-3, -4))
        '
        Console.ReadLine()
    End Sub
    Function GetRow(ByVal value1 As Integer, _
                    ByVal value2 As Integer) As String
        If value1 > value2 Then
            GetRow = GetRow(value2, value1)
        ElseIf value2 - value1 < 2 Then
            GetRow = ""
        Else
            GetRow = (value1 + 1) & " " & GetRow(value1 + 1, value2)
        End If
    End Function
End Module

Download Visual Basic 2010 Broncode Download Visual C# Sourcecode

Opgave :

Breid onderstaande programmacode uit met de recursieve procedure PlaceSteps.

Visual Basic 2010 Broncode

Module Exercise3Task
    Sub Main()
        'PlaceSteps(2)
        Console.WriteLine()
        '
        'PlaceSteps(10)
        Console.WriteLine()
        '
        'PlaceSteps(11)
        Console.ReadLine()
    End Sub
End Module

Download Visual Basic 2010 Broncode Download Visual C# Sourcecode

Console Application Output

Oplossing :

Visual Basic 2010 Broncode

Module Exercise3Solution
    Sub Main()
        PlaceSteps(2)
        Console.WriteLine()
        '
        PlaceSteps(10)
        Console.WriteLine()
        '
        PlaceSteps(11)
        Console.ReadLine()
    End Sub
    Sub PlaceSteps(ByVal distance As Integer)
        Dim stepDistance As Integer
        If distance = 1 Then
            stepDistance = 1
            Console.WriteLine(stepDistance)
        Else
            If distance >= 3 Then
                stepDistance = 3
            ElseIf distance >= 1 Then
                stepDistance = 1
            End If
            Console.WriteLine(stepDistance)
            PlaceSteps(distance - stepDistance)
        End If
    End Sub
End Module

Download Visual Basic 2010 Broncode Download Visual C# Sourcecode

Opgave :

Breid onderstaande programmacode uit met de recursieve functie BinarySearch. Die via de "Binary Search" methode op zoek gaat naar een bepaald getal in een gesorteerde tabel.

Visual Basic 2010 Broncode

Module Exercise4Task
    Sub Main()
        Dim numbers As Integer() = {1, 3, 4, 7, 9, 10, 11, 15, 18, 20}
        '
        Dim number, lowerbound, upperbound As Integer
        Dim found As Boolean
        '
        number = 15
        lowerbound = 0
        upperbound = 9
        'found = BinarySearch(number, numbers, lowerbound, upperbound)
        Console.WriteLine(found)
        '
        number = 18
        lowerbound = 0
        upperbound = 7
        'found = BinarySearch(number, numbers, lowerbound, upperbound)
        Console.WriteLine(found)
        '
        Console.ReadLine()
    End Sub
End Module

Download Visual Basic 2010 Broncode Download Visual C# Sourcecode

Console Application Output

True
False

Oplossing :

Visual Basic 2010 Broncode

Module Exercise4Solution
    Sub Main()
        Dim numbers As Integer() = {1, 3, 4, 7, 9, 10, 11, 15, 18, 20}
        '
        Dim number, lowerbound, upperbound As Integer
        Dim found As Boolean
        '
        number = 15
        lowerbound = 0
        upperbound = 9
        found = BinarySearch(number, numbers, lowerbound, upperbound)
        Console.WriteLine(found) ' True
        '
        number = 18
        lowerbound = 0
        upperbound = 7
        found = BinarySearch(number, numbers, lowerbound, upperbound)
        Console.WriteLine(found) ' False
        '
        Console.ReadLine()
    End Sub
    Function BinarySearch(ByVal number As Integer, _
                          ByVal array As Integer(), _
                          ByVal lowerbound As Integer, _
                          ByVal upperbound As Integer) As Boolean
        Dim middle As Integer = (lowerbound + upperbound) \ 2
        If (number = array(middle)) Then
            BinarySearch = True
        Else
            If (upperbound <= lowerbound) Then
                BinarySearch = False
            Else
                If number > array(middle) Then
                    lowerbound = middle + 1
                Else
                    upperbound = middle - 1
                End If
                BinarySearch = BinarySearch(number, array, lowerbound, upperbound)
            End If
        End If
    End Function
End Module

Download Visual Basic 2010 Broncode Download Visual C# Sourcecode

Opgave :

Breid onderstaande programmacode uit met de recursieve procedure TowersOfHanoi.

De procedure zou moeten weergeven welke stappen moeten ondernomen worden om het "Torens van Hanoi"-probleem om te lossen.

In dit probleem moet een bepaald aan schijven - van verschillende grote - verplaatst worden. Dit vertrekkende van een bepaalde bronstaaf, via een bepaalde hulpstaaf, naar een bepaald doelstaaf.
De beperkingen zijn hierbij dat je slechts 1 schijf per keer mag verplaatsen en dat je nooit een grotere schijf op een kleinere mag plaatsen.

Bij het probleem "Torens van Hanoi" is het de bedoeling op zoek te gaan naar het minimum aantal verplaatsingen.

Zorg ervoor dat de procedure afdrukt welke verplaatsingen moeten gebeuren.

Visual Basic 2010 Broncode

Module Exercise5Task
    Sub Main()
        Dim diskCount As Integer = 5
        Dim source As Integer = 1
        Dim help As Integer = 2
        Dim destination As Integer = 3
        '
        'TowersOfHanoi(diskCount, source, destination, help)
        '
        Console.ReadLine()
    End Sub
End Module

Download Visual Basic 2010 Broncode Download Visual C# Sourcecode

Console Application Output

from 1 to 3
from 1 to 2
from 3 to 2
from 1 to 3
from 2 to 1
from 2 to 3
from 1 to 3
from 1 to 2
from 3 to 2
from 3 to 1
from 2 to 1
from 3 to 2
from 1 to 3
from 1 to 2
from 3 to 2
from 1 to 3
from 2 to 1
from 2 to 3
from 1 to 3
from 2 to 1
from 3 to 2
from 3 to 1
from 2 to 1
from 2 to 3
from 1 to 3
from 1 to 2
from 3 to 2
from 1 to 3
from 2 to 1
from 2 to 3
from 1 to 3

Oplossing :

Visual Basic 2010 Broncode

Module Exercise5Solution
    Sub Main()
        Dim diskCount As Integer = 5
        Dim source As Integer = 1
        Dim help As Integer = 2
        Dim destination As Integer = 3
        '
        TowersOfHanoi(diskCount, source, destination, help)
        '
        Console.ReadLine()
    End Sub
    Sub TowersOfHanoi(ByVal diskCount As Integer, _
                      ByVal source As Integer, ByVal destination As Integer, _
                      ByVal help As Integer)
        If diskCount = 1 Then
            Console.WriteLine("from " & source & " to " & destination)
        Else
            TowersOfHanoi(diskCount - 1, source, help, destination)
            Console.WriteLine("from " & source & " to " & destination)
            TowersOfHanoi(diskCount - 1, help, destination, source)
        End If
    End Sub
End Module

Download Visual Basic 2010 Broncode Download Visual C# Sourcecode

Opgave :

Breid onderstaande programmacode uit met de recursieve functie GetFiboNumbers.

Visual Basic 2010 Broncode

Module Exercise6Task
    Sub Main()
        Dim fiboNumbers As Integer()
        'fiboNumbers = GetFiboNumbers(10)
        '
        For Each fiboNumber As Integer In fiboNumbers
            Console.Write(fiboNumber & " ")
        Next
        '
        Console.ReadLine()
    End Sub
End Module

Download Visual Basic 2010 Broncode Download Visual C# Sourcecode

Console Application Output

1 1 2 3 5 8 13 21 34 55

Oplossing :

Visual Basic 2010 Broncode

Module Exercise6Solution
    Sub Main()
        Dim fiboNumbers As Integer()
        fiboNumbers = GetFiboNumbers(10)
        '
        For Each fiboNumber As Integer In fiboNumbers
            Console.Write(fiboNumber & " ")
        Next
        '
        Console.ReadLine()
    End Sub
    Function GetFiboNumbers(ByVal ordinal As Integer) As Integer()
        Dim fiboNumbers As Integer()
        If ordinal = 1 Then
            fiboNumbers = New Integer() {1}
        ElseIf ordinal = 2 Then
            fiboNumbers = New Integer() {1, 1}
        ElseIf ordinal > 2 Then
            fiboNumbers = GetFiboNumbers(ordinal - 1)
            ReDim Preserve fiboNumbers(ordinal - 1)
            fiboNumbers(ordinal - 1) = fiboNumbers(ordinal - 2) + _
                                       fiboNumbers(ordinal - 3)
        End If
        GetFiboNumbers = fiboNumbers
    End Function
End Module

Download Visual Basic 2010 Broncode Download Visual C# Sourcecode

Dit artikel is gepubliceerd op zondag 31 juli 2011 op vbvoorbeelden, bezoek de website voor een recente versie van dit artikel of andere artikels.

hoofdstuk	7. Arrays 8. Procedures en Functies 9. Object Oriented Programming
onderwerp	8.13. Parameter Arrays - ParamArray 8.14. Recursie 9.1. Inleiding Object Oriented Programming
broncode	Download Recursie.vb of Recursie.cs
datum	laatst gewijzigd op dinsdag 21 april 2009, laatst gepubliceerd op zondag 31 juli 2011

visual basic 2010 broncode voorbeelden

8.14. Recursie

8.14.1. Faculteitsberekening

8.14.2. Bepalen van de Grootste Gemene Deler

8.14.3. Machtsverheffing

8.14.4. Fibonacci

8.14.5. Quick Sort

8.14.6. Backtracking

8.14.7. Oefeningen

8.14.1. Faculteitsberekening

8.14.2. Bepalen van de Grootste Gemene Deler

8.14.3. Machtsverheffing

8.14.4. Fibonacci

8.14.5. Quick Sort

8.14.6. Backtracking

8.14.7. Oefeningen