CUBE.CODES: Rekursion

Programm 1: Wie vermehren sich die Karnickel? - Die Fibonacci-Folge

>>> direkt zu CUBE.CODES

altalt=1; 
alt=1;
neu=2;  
UI.log(altalt);
UI.log(alt);
UI.log(neu);

while(neu<1000000000) {
	altalt=alt;
	alt=neu;
	neu=altalt+alt;
	UI.log(neu);
}

Ausgabe:

[16:01:28] Program starting ...
[16:01:28] Program running ...
1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
6765
10946
17711
28657
46368
75025
121393
196418
317811
514229
832040
1346269
2178309
3524578
5702887
9227465
14930352
24157817
39088169
63245986
102334155
165580141
267914296
433494437
701408733
1134903170
[16:01:29] Program finished successfully

Bei der etwas unübersichtlichen Umschichtung von den beiden Vorgängerwerten und dem Neuwert von einem zum nächsten Rechenschritt muss man höllisch aufpassen, dass man nicht einen Wert überschreibt, den man später noch braucht! Daher wirkt der Code etwas umständlich. Außerdem ist es komisch, dass man immer alle Vorgänger ausrechnen muss, wenn man vielleicht nur am 40. Wert interessiert ist!

Genial einfach dagegen ist die folgende Definition:

Wir sagen einfach: Berechne F(40), indem Du F(39) und F(38) addierst.

Klappt das wirklich?

Auch wenn das stimmt, ist ja F grade mit 40 beschäftigt und kann nicht fertig rechnen, weil F auf einmal vorher den Wert für 38 und 39 berechnen muss. So eine Definition klappt in JavaScript, aber nicht in allen Programmiersprachen, denn wir muten CUBE.CODES ganz schön was zu: CUBE.CODES muss die Berechnung von F(40) unterbrechen (alles sich merken, um danach fertig zu rechnen), F(38) und F(39) beginnen zu berechnen, ...

aber da wird die Berechnung ja wieder unterbrochen, um vorher F(36), F(37) und F(37), F(38) auszurechnen!

...

Die meisten modernen Programmiersprachen managen sowas. Man nennt dieses Vorgehen Rekursion. Den Stapel noch offener, unvollständiger Rechnungen nennt man Stack. Der ist nicht unbegrnzt, aber heutzutage ganz schön tolerant!

Programm 2: Wie vermehren sich die Karnickel? - Die Fibonacci-Folge mit Rekursion

>>> direkt zu CUBE.CODES

function F(x) { if(x<3) return(1); else return(F(x-2)+F(x-1)); }
for(i=1; i<40; ++i) UI.log("F(" + i + ")=" + F(i)); 

Der kurze Zweizeiler ist schon extrem cool. Aber das Dröppeln der Ergebnisse ab 35 lässt nachdenken!

Ausgabe:

[15:50:55] Program starting ...
[15:50:56] Program running ...
F(1)=1
F(2)=1
F(3)=2
F(4)=3
F(5)=5
F(6)=8
F(7)=13
F(8)=21
F(9)=34
F(10)=55
F(11)=89
F(12)=144
F(13)=233
F(14)=377
F(15)=610
F(16)=987
F(17)=1597
F(18)=2584
F(19)=4181
F(20)=6765
F(21)=10946
F(22)=17711
F(23)=28657
F(24)=46368
F(25)=75025
F(26)=121393
F(27)=196418
F(28)=317811
F(29)=514229
F(30)=832040
F(31)=1346269
F(32)=2178309
F(33)=3524578
F(34)=5702887
F(35)=9227465
F(36)=14930352
F(37)=24157817
F(38)=39088169
F(39)=63245986
[15:50:58] Program finished successfully

Anregungen, Aufgaben:

• Taste Dich mal langsam an höhere Werte ran!
• Die Rechenzeit von einem zum nächsten Schritt verdoppelt sich jedes Mal!
• Ab 42 wird's langsam zäh.
• Irgendwann ist auch der Stack übervoll. Er muss sich ja Millionen offener Aufgaben merken!
• Wie viele Funktionsaufrufe braucht CUBE.CODES, um das Ergebnis F(39) mit Rekursion zu berechnen?
• Wie viele Rechenschritte brauchte Programm 1, um dasselbe Ergebnis zu berechnen?
• Nur F(45) zu berechnen (und die Ausgaben aller Vorgänger wegzulassen), bringt nicht wirklich die große Erleichterung