Rekursion bedeutet wörtlich „Rücklauf“.
Die einfachste Form der Rekursion ist eine Funktion die sich selbst aufruft. Um nicht in einer Endlosschleife zu enden, muss bei einer Rekursion eine Abbruchbedingung definiert werden, bevor der rekursive Aufruf erfolgt.
Der Aufruf erfolgt also mit entsprechenden Startparametern und wird durch definierte Bedingungen abgebrochen werden.
Solange die Abbruchbedingung nicht zutrifft, erhöht sich bei jedem Durchlauf die Rekursionstiefe.
Funktion(Parameter)
if Parameter <> Bedingung
Funktion(Parameter)
endif
FunktionEnde
Lineare Rekursion:
Am häufigsten wird wohl die lineare Rekursion genutzt. Hierbei kommt in jedem Fall nur ein rekursiver Aufruf vor. Die Berechnung erfolgt dann entlang einer Kette von Aufrufen.
Für solche Fälle gibt es meistens eine iterative (Schleifen) Lösung.
; Rekursiv die Länge einer Zeichenkette ermitteln
EnableExplicit
Define sString.s
Define *PtoStr.i
Define Sum.i
sString = "Hallo" ; String dessen Zeichen gezählt werden sollen
Procedure.i SummeChar(*PtoStr)
Protected Sum.i, *cChar.Character
;CallDebugger
*cChar = *PtoStr
;Debug Chr(*cChar\c)
if Chr(*cChar\c) › "" ; Die Ausführungsbedingung lautet hier: Parameterwert muß ein Zeichen enthalten
*PtoStr+SizeOf(Character) ; Der Adresswert wird um eine Zeichenlänge erhöht
Sum = SummeChar(*PtoStr.i) ; hier wird die Prozedur mit einem Adresswert + einer Zeichenlänge aufgerufen
Sum +1 ; Der Summenwert wird um 1 erhöht; dies geschieht erst beim Rücklauf!
; Debug "Prozeduraufruf "+Str(Sum)
; Debug "Sum hat den Wert "+Str(Sum)
; Debug "Die Summe beträgt jetzt "+Str(Sum)
; Debug ""
ProcedureReturn Sum ; und gibt die Summe als Rückgabewert zurück
else
ProcedureReturn 0 ; ansonsten wird 0 zurück gegeben
EndIf
EndProcedure
*PtoStr = @sString ; Die Adresse des Strings wird dem Pointer *PtoStr zugewiesen
Sum = SummeChar(*PtoStr)
debug "Der String "+sString+" hat "+Str(Sum)+" Buchstaben!"
Bei der primitiven Rekursion, die ebenfalls zu den linearen Rekursionen gehört, definiert man eine Funktion der natürlichen Zahlen, deren erster Parameter bei jedem Aufruf um Eins ab- oder zunimmt.
; primitive Rekursion
EnableExplicit
Define n.i
Define Sum.i
n = 3 ; Zahl aus der die Summe erechnet werden soll
Procedure.i Summe(n.i)
Protected Sum.i
;CallDebugger
if n › 0 ; Die Ausführungsbedingung lautet hier: Parameterwert größer 0
Sum = n + Summe(n-1) ; hier ruft sich die Prozedur mit einem Parameterwert-1 selbst auf
Debug "Prozeduraufruf "+Str(n)
Debug "n hat den Wert "+Str(n)
Debug "Die Summe beträgt jetzt "+Str(Sum)
Debug ""
ProcedureReturn Sum ; und gibt die Summe als Rückgabewert zurück
else
ProcedureReturn 0 ; ansonsten wird 0 zurück gegeben
EndIf
EndProcedure
Sum = Summe(n)
debug "Die Summe aller Zahlen von "+Str(n)+" lautet "+Str(Sum)
; Für solche Fälle gibt es meistens eine iterative (Schleifen) Lösung oder eine rekursive (Rücklauf, Selbstaufruf) Methode
;Sum = n*(n+1)/2 ; nach der Gaußschen Summenformel läßt sich die Summe
; ; einer Zahlenreihe auch ohne Rekursion berechnen
Ein weiteres Beispiel ist die Berechnung der Fakultät (das Produkt aller Zahlen) einer Zahl.
; Rekursive Fakultätsberechnung
EnableExplicit
Define n.i
Define F.i
n = 5 ; Zahl von der die Fakultät erechnet werden soll
Procedure.i Fakultaet(n.i)
Protected F.i
;CallDebugger
if n › 1 ; Die Ausführungsbedingung lautet hier: Parameterwert größer 1
F = n * Fakultaet(n-1) ; hier ruft sich die Prozedur mit einem Parameterwert-1 selbst auf
Debug "Prozeduraufruf "+Str(n)
Debug "n hat den Wert "+Str(n)
Debug "Die Fakultät hat jetzt den Wert "+Str(F)
Debug ""
ProcedureReturn F ; und gibt die Fakultät als Rückgabewert zurück
else
ProcedureReturn 1 ; ansonsten wird 1 zurück gegeben
EndIf
EndProcedure
F = Fakultaet(n)
debug "Die Fakultät von "+Str(n)+" lautet "+Str(F)
Verschachtelte Rekursion:
Die verschachtelte Rekursion enthält in den Parametern der Funktionsaufrufe wiederum rekursive Funktionsaufrufe. Diese Art der Rekursion ist schwer durchschaubar.
; verschachtelte Rekursion
EnableExplicit
Define n.i
Define m.i
Procedure Funktion(m.i,n.i)
Debug "Funktion("+ Str(m)+", "+ Str(n)+")"
if m ‹ n:
ProcedureReturn 0
else
if (n = 0) or (m = n)
ProcedureReturn 1
else
ProcedureReturn (Funktion(m-1, n-1) + Funktion(m-1, n))
EndIf
EndIf
EndProcedure
Funktion(5,3)
Kaskadenartige Rekursion:
Bei der kaskadenartigen Rekursion folgen mehrere rekursive Aufrufe aufeinander. Die Entfaltung der Aufrufe gleicht einem Baum. Sie kann sehr schnell zu einem sehr großem Rechenaufwand führen.
Ein sehr schönes Beispiel dafür ist sicher der sogenannte Pythagoras-Baum.
Er basiert auf einem einfachen Regelwerk:
Gegeben sind zwei Punkte. Auf diesen wird ein Quadrat errichtet. Auf diesem Quadrat wiederum ein Dreieck mit definierten Winkeln oder Seiten. Für jede der beiden offenen Seiten des Dreiecks wird wieder die Funktion aufgerufen. Je nach Rekursionstiefe ergibt sich dann ein baumähnliches Gebilde.
; Pythagoras-Baum
EnableExplicit
If InitSprite() = 0 Or InitKeyboard() = 0 or InitMouse() = 0
MessageRequester("Error", "Can't open DirectX 7 or later", 0)
End
EndIf
Structure pPunkte
P1.POINT
P2.POINT
EndStructure
Procedure AlterGriechenBaum(x1.i, y1.i, x2.i, y2.i, n.i)
Protected Distance.i, DiffX.i, DiffY.i
Protected P1.POINT, P2.POINT, P3.POINT
Protected fWinkelP.f,Winkel.i, fWinkelD.f
if n › 0 ; Die Ausführungsbedingung lautet hier: Rekursionstiefe > 0
NewList lPunkte.pPunkte()
DiffX = x2-x1
DiffY = y2-y1
Distance = Sqr(DiffX*DiffX+DiffY*DiffY)
Winkel = ACos(DiffX/Distance)*57.29577
If y1‹y2 : Winkel=360-Winkel : EndIf
fWinkelP =(Winkel +180) *(2*3.14159265/360);Winkel für Quadrat
fWinkelD =(Winkel +150) *(2*3.14159265/360);Winkel für Dreieck
P1\x = Round(x1 + (Distance * Sin(fWinkelP)),0)
P1\y = Round(y1 + (Distance * Cos(fWinkelP)),0)
P2\x = Round(x2 + (Distance * Sin(fWinkelP)),0)
P2\y = Round(y2 + (Distance * Cos(fWinkelP)),0)
P3\x = Round(P1\x + ((Distance/2) * Sin(fWinkelD)),0)
P3\y = Round(P1\y + ((Distance/2) * Cos(fWinkelD)),0)
; Box zeichnen
LineXY(P1\x,P1\y,x1,y1,$FFFFFF)
LineXY(P2\x,P2\y,x2,y2,$FFFFFF)
LineXY(P1\x,P1\y,P2\x,P2\y,$40FF00)
LineXY(x1,y1,x2,y2,$FFFFFF)
; Dreieck zeichnen
LineXY(P1\x,P1\y,P3\x,P3\y,$40FF00)
LineXY(P2\x,P2\y,P3\x,P3\y,$40FF00)
; Punkte in der Liste speichern
; Linke Seite vom Dreieck
AddElement(lPunkte())
lPunkte()\P1\x = P1\x
lPunkte()\P1\y = P1\y
lPunkte()\P2\x = P3\x
lPunkte()\P2\y = P3\y
; Rechte Seite vom Dreieck
AddElement(lPunkte())
lPunkte()\P1\x = P3\x
lPunkte()\P1\y = P3\y
lPunkte()\P2\x = P2\x
lPunkte()\P2\y = P2\y
ForEach lPunkte()
AlterGriechenBaum(lPunkte()\P1\x,lPunkte()\P1\y,lPunkte()\P2\x,lPunkte()\P2\y,n-1);Aufruf mit Rekursionstiefe-1
Next
ClearList(lPunkte())
EndIf
EndProcedure
; Test
Define POINTA.POINT, POINTB.POINT
Define Hoehe.i, hwnd.i, Event.i
Define WinX.i, WinY.i, WinWidth.i, WinHeight.i
Define ScreenX.i, ScreenY.i, ScreenWidth.i, ScreenHeight.i
Define n.i
WinX = 0: WinY = 0: WinWidth = 600: WinHeight = 600
ScreenX = 0: ScreenY = 0: ScreenWidth = WinWidth: ScreenHeight = WinHeight
POINTA\x = 240: POINTA\y = 500
POINTB\x = 310: POINTB\y = 500
n = 10 ; Rekursionstiefe
hwnd = OpenWindow(0, WinX, WinY, WinWidth, WinHeight, "Pythagoras-Baum", #PB_Window_ScreenCentered | #PB_Window_SystemMenu)
If OpenWindowedScreen(hwnd,ScreenX,ScreenY,ScreenWidth,ScreenHeight,0,0,0)
StartDrawing(ScreenOutput())
AlterGriechenBaum(POINTA\x,POINTA\y,POINTB\x,POINTB\y,n)
StopDrawing()
FlipBuffers()
Repeat
Repeat
Select WindowEvent ()
Case #PB_Event_CloseWindow
End
Case #Null
Break
EndSelect
ForEver
ExamineKeyboard()
Delay(1)
Until Event = #PB_Event_CloseWindow Or KeyboardPushed(#PB_Key_Escape)
End
Else
MessageRequester("Fehler","Konnte Screen nicht öffnen")
End
EndIf
Ich hoffe das diese Erläuterungen für einige etwas hilfreich waren.
