CUBE.CODES: Rekursion: Unterschied zwischen den Versionen
| Zeile 88: | Zeile 88: | ||
function F(x) { if(x<3) return(1); else return(F(x-2)+F(x-1)); } | function F(x) { if(x<3) return(1); else return(F(x-2)+F(x-1)); } | ||
| − | + | UI.log("F(39)=" + F(39)); | |
Der kurze Zweizeiler ist schon extrem cool. Aber das Dröppeln der Ergebnisse ab 35 läßt nachdenken! | Der kurze Zweizeiler ist schon extrem cool. Aber das Dröppeln der Ergebnisse ab 35 läßt nachdenken! | ||
Version vom 27. April 2021, 16:41 Uhr
Programm 1: Wie vermehren sich die Karnickel? - Die Fibonacci-Folge
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!
Außerdem braucht man die Vorgänger nimmer, wenn man F(39) berechnet!
Programm 2: Wie vermehren sich die Karnickel? - Die Fibonacci-Folge mit Rekursion
function F(x) { if(x<3) return(1); else return(F(x-2)+F(x-1)); }
UI.log("F(39)=" + F(39));
Der kurze Zweizeiler ist schon extrem cool. Aber das Dröppeln der Ergebnisse ab 35 läßt 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
