Abflachen von Rekursion

(Tutorial)

Bei einigen Programmen ist es nötig, das Rekursion eingesetzt wird. Nur da gibt es ein kleines Problem: Der ClassPad kann zwar Selbst-Aufrufe (d.h. ein Programm kann sich selber aufrufen). Jedoch fehlt eine Rückgabe-Funktion um Werte aus der tieferen Rekursions-Ebene zurück zu geben.
Dieses kann mit einer Liste dem zugehörigem Index umgangen werden. Bei jedem Aufruf wird dann der Index erhöht. Nachdem die Funktion wieder zurückgekehrt ist, wird der Index wieder verringert. Dadurch bleibt in jeder Tiefe im Verlauf des Programmabluafs der aktuelle Index gleich.

Als Beispiel sollen die Fibonacci-Zahlen dienen. Diese kann man rekursiv mit a_n = a_n-1 + a_n-2 und a₀ = a₁ = 1 berechnen.

Das Start-Programm könnte wie folgt aussehen:

'Name: Fibo
'Parameter: n
'Der Speicher
fill(0, 20)F
'Der Index
0tF
'Parameter weiterreichen
F(n)
'Ausgabe
ClrText
'tF sollte nun 1 sein
Print F[tF]

Dadurch wird der Speicher (die Liste) und der Index auf 0 gesetzt. Das Programm, welches die Rekursion ausführt könnte dann wie folgt aussehen:

'Name: F
'Parameter: n
'Index erhöhen
tF+1tF

If n<0
Then
Message "Fehler. Negativer Parameter"
Stop
IfEnd
If n=0 or n=1
Then
'Die Start-Werte
1F[tF]
IfEnd
If n>1
Then
F(n-1)
F(n-2)
'zwei Aufrufe - Index um zwei verringern
tF-2tF
'Berechnen
'F(n-1)       + F(n-2)
F[tF+1]+F[tF+2]F[tF]
IfEnd

Um nun die Berechnung durchzuführen ruft man das Start-Programm auf. Das tF+1 und tF+2 in der vorletzten Code-Zeile liegt daran, das der "Hilfs-Stack" mit aufsteigendem Index gezählt wird. D.h. eine tiefere Rekursions-Ebene hat einen Höheren Index.

Das folgende Bild zeigt für den Parameter 4 die Belegung des Stacks. Wobei sich das Programm erst bis zur unteren Ebene selbst aufruft und dann die Werte berechnet. Am Ende bleibt das Start-Programm bei Tiefe 1 stehen.