HBLogon.gif
Rekursion - erwünschte Wiederholungen
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


; 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.