CUBE.CODES: Rekursion: Unterschied zwischen den Versionen
Zur Navigation springen
Zur Suche springen
| Zeile 68: | Zeile 68: | ||
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'''! | 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 | + | Genial einfach dagegen ist die folgende Definition: |
| − | Wir sagen einfach: '''Berechne F(40), indem Du F(39) und F(38) addierst'''. 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. | + | 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. | ||
===Programm 2: Wie vermehren sich die Karnickel? - Die Fibonacci-Folge mit Rekursion=== | ===Programm 2: Wie vermehren sich die Karnickel? - Die Fibonacci-Folge mit Rekursion=== | ||
Version vom 27. April 2021, 15:13 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.
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)); }
for(i=1; i<40; ++i) UI.log("F(" + i + ")=" + F(i));
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
Aufgabe:
- 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?
