Wenn ich das dann richtig interpretiere, hätte die Rekursive Methode eine O-Notation von O(2^n) wenn n>0 Zur Rekursionstiefe habe ich ebenfalls eine Frage. Sie meinten, dass die Tiefe bestimmt wird, durch die Anzahl der Aufrufe+1. Der Stackoverflow würde ja deshalb kommen, weil der GC ja den Speicher nicht bereinigen kann, da da noch Referenzadressen offen sind. Demnach ist ja das durchschleifen von Variablen zu x-Methoden Bad Practice und besser durch Objektrefernzierung zu ersetzen.
Was genau meinen Sie denn mit "Rekursive Methode"? Es kommen ja mehrere Algorithmen im Video vor. Ich würde nicht so weit gehen zu sagen, das "Durchschleifen" von Funktionsargumenten bei rekursiven Funktionen "bad practice" zu nennen. Letztlich kommen Sie bei extrem großen Rekursionstiefen um den Überlauf des Stacks kaum herum, selbst wenn Sie der Funktion gar keine Argumente übergeben und auch keine lokalen Variablen benutzen. Gewöhnlich sind Funktionen in Programmiersprachen so gestrickt, dass es möglich ist, sie von mehrere Orten im Programm aus aufzurufen. Sobald eine Funktion beendet wird, muss sie zu ihrer Aufrufstelle zurückkehren. Wenn es dann mehrere mögliche solche Stellen gibt, muss zur Laufzeit gespeichert, von wo aus der letzte Aufruf getätigt worden ist - und genau dafür bietet sich ein Stack an. Dieser Stack wird sich also bei steigender Rekursionstiefe immer weiter füllen und irgendwann unweigerlich überlaufen. Einzig bei speziell für Rekursion optimierten (funktionale) Programmiersprachen mag das evtl. anders sein.
@@Gogol-Doering Hallo und danke für die rasche Antwort. Im Beispiel 3 Erklären Sie, dass durch wieder aufrufen der Methode eine Rekursionstiefe erreicht wird und das Programm irgendwann durch das wieder und wieder aufrufen der Methode im Stack, dadurch dass neue Elemente hinzu kommen. Aber zur Erklärung meiner Frage, die bezog sich eher auf das Beispiel 4, da in der Methode "Riddle". Aber nach erneuten Überlegen, kann dieser Algorithmus gar nicht O(2^n) besitzen. "Ich würde nicht so weit gehen zu sagen, das "Durchschleifen" von Funktionsargumenten bei rekursiven Funktionen "bad practice" zu nennen" --> Daher meinte ich das ja mit Bad-Practice. Weshalb ich das ansprach, ist weil ein MA bei uns so programmiert, dass Funktionsaufrufe ineinander Verschachtelt sind. Daher interessiert mich das Thema auch sehr, sowie das genauere und bessere Verständnis von der O-Notation, wobei man hier lediglich nur Teilabschnitte bewerten kann.?
@@tomatentheo7198 Tatsächlich ist die Abschätzung von Laufzeiten rekursiver Algorithmen oft nicht so einfach. Bei manchen rekursiven Algorithmen kann man dafür z.B. das Mastertheorem anwenden, bei anderen geht das nicht, und manchmal bekommt man sogar echte Probleme. Der Algorithmus "riddle" (Beispiel 4) im Video ist jedoch ein Algorithmus, bei dem die Laufzeit ziemlich leicht bestimmt werden kann: Wenn Sie den Algorithmus mit einem n aus N0 aufrufen, dann wird es in der Folge für jedes kleinere n aus N0 jeweils genau ein rekursiver Aufruf ausgelöst. Insgesamt gibt es dann also n+1 Aufrufe von riddle. Da jeder einzelne Aufruf für sich betrachtet (also wenn man einmal andere rekursive Aufrufe weg lässt) nur konstant viel Zeit benötigt, ist die Gesamtlaufzeit des Aufrufs also linear O(n). Damit stimmt tatsächlich auch O(n^2), auch wenn dies keine enge obere Abschätzung für die Laufzeit wäre.
Bei mir bricht der Code ohne StackOverflow ab, weil Scala keinen NumberUnderflow wirft, wenn man bei Int.MIN_VALUE angelangt ist. Läuft ca. 2s auf einem nicht ganz taufrischen Laptop. scala> @tailrec | def htn (n: Int) : Int = { | if (n == 32) return n else return htn(n-1) } htn: (n: Int)Int scala> htn (30) res7: Int = 32 Der Compiler kann bei endrekursiven Funktionen diese optimieren und einen Stackoverflow vermeiden. Das Schlüsselwort @tailrec weist den Compiler an, eine Fehlermeldung auszugeben, sollte es nicht endrekursiv sein.
Interessant, das wusste ich gar nicht. Aber Scala ist als funktionale Programmiersprache natürlich auf Rekursion hin optimiert. In meinem Video hatte ich eher "old school"-Programmiersprachen wie z.B. C/C++ im Kopf, bei denen die Programme bei zu großer Rekursionstiefe einfach "unfreundlich" abschmieren. :)
@@Gogol-Doering Das ist m.W. keine Frage des Alters, aber (ohne Gewähr, nicht überprüft!) Lisp sollte das ähnlich handhaben - mag aber auch sein, dass bei neueren Lispversionen verschiedene Features erst dazukamen, d.h. ein Test mit einem aktuellen Lisp würde auch keine Gewähr dafür bieten, dass das schon 1970 bei Lisp so war. :)
Hab in meinLispscript geschaut und racket(drracket angeworfen: (define (htn n) (if (= n 32) n (htn (- n 1)) ) ) (htn 30) Läuft ewig (> 1h). Statt die Doku zu lesen mach ich lieber ein rasches, schmutziges Experiment. Scheint, als seien Integers nicht Größenlimitiert, zumindest nicht zu einer 32-bit-Größe, sonst wär's in 60 min wohl fertig geworden. Aber auch kein Stacküberlauf.
Der Witz am Anfang war echt gut 😂
Der Witz steht in einigen Büchern. Unter Rekursion in den Sachregistern / im Index. ;)
Danke, hilft mir sehr mich auf meinen Test vorzubereiten 👍
Ist auch sehr schülerfreundlich, gut erklärt :)
Wenn ich das dann richtig interpretiere, hätte die Rekursive Methode eine O-Notation von O(2^n) wenn n>0
Zur Rekursionstiefe habe ich ebenfalls eine Frage. Sie meinten, dass die Tiefe bestimmt wird, durch die Anzahl der Aufrufe+1. Der Stackoverflow würde ja deshalb kommen, weil der GC ja den Speicher nicht bereinigen kann, da da noch Referenzadressen offen sind.
Demnach ist ja das durchschleifen von Variablen zu x-Methoden Bad Practice und besser durch Objektrefernzierung zu ersetzen.
Was genau meinen Sie denn mit "Rekursive Methode"? Es kommen ja mehrere Algorithmen im Video vor.
Ich würde nicht so weit gehen zu sagen, das "Durchschleifen" von Funktionsargumenten bei rekursiven Funktionen "bad practice" zu nennen. Letztlich kommen Sie bei extrem großen Rekursionstiefen um den Überlauf des Stacks kaum herum, selbst wenn Sie der Funktion gar keine Argumente übergeben und auch keine lokalen Variablen benutzen. Gewöhnlich sind Funktionen in Programmiersprachen so gestrickt, dass es möglich ist, sie von mehrere Orten im Programm aus aufzurufen. Sobald eine Funktion beendet wird, muss sie zu ihrer Aufrufstelle zurückkehren. Wenn es dann mehrere mögliche solche Stellen gibt, muss zur Laufzeit gespeichert, von wo aus der letzte Aufruf getätigt worden ist - und genau dafür bietet sich ein Stack an. Dieser Stack wird sich also bei steigender Rekursionstiefe immer weiter füllen und irgendwann unweigerlich überlaufen. Einzig bei speziell für Rekursion optimierten (funktionale) Programmiersprachen mag das evtl. anders sein.
@@Gogol-Doering Hallo und danke für die rasche Antwort. Im Beispiel 3 Erklären Sie, dass durch wieder aufrufen der Methode eine Rekursionstiefe erreicht wird und das Programm irgendwann durch das wieder und wieder aufrufen der Methode im Stack, dadurch dass neue Elemente hinzu kommen.
Aber zur Erklärung meiner Frage, die bezog sich eher auf das Beispiel 4, da in der Methode "Riddle". Aber nach erneuten Überlegen, kann dieser Algorithmus gar nicht O(2^n) besitzen.
"Ich würde nicht so weit gehen zu sagen, das "Durchschleifen" von Funktionsargumenten bei rekursiven Funktionen "bad practice" zu nennen" --> Daher meinte ich das ja mit Bad-Practice. Weshalb ich das ansprach, ist weil ein MA bei uns so programmiert, dass Funktionsaufrufe ineinander Verschachtelt sind. Daher interessiert mich das Thema auch sehr, sowie das genauere und bessere Verständnis von der O-Notation, wobei man hier lediglich nur Teilabschnitte bewerten kann.?
@@tomatentheo7198
Tatsächlich ist die Abschätzung von Laufzeiten rekursiver Algorithmen oft nicht so einfach. Bei manchen rekursiven Algorithmen kann man dafür z.B. das Mastertheorem anwenden, bei anderen geht das nicht, und manchmal bekommt man sogar echte Probleme. Der Algorithmus "riddle" (Beispiel 4) im Video ist jedoch ein Algorithmus, bei dem die Laufzeit ziemlich leicht bestimmt werden kann: Wenn Sie den Algorithmus mit einem n aus N0 aufrufen, dann wird es in der Folge für jedes kleinere n aus N0 jeweils genau ein rekursiver Aufruf ausgelöst. Insgesamt gibt es dann also n+1 Aufrufe von riddle. Da jeder einzelne Aufruf für sich betrachtet (also wenn man einmal andere rekursive Aufrufe weg lässt) nur konstant viel Zeit benötigt, ist die Gesamtlaufzeit des Aufrufs also linear O(n). Damit stimmt tatsächlich auch O(n^2), auch wenn dies keine enge obere Abschätzung für die Laufzeit wäre.
Bei mir bricht der Code ohne StackOverflow ab, weil Scala keinen NumberUnderflow wirft, wenn man bei Int.MIN_VALUE angelangt ist. Läuft ca. 2s auf einem nicht ganz taufrischen Laptop.
scala> @tailrec
| def htn (n: Int) : Int = {
| if (n == 32) return n else return htn(n-1) }
htn: (n: Int)Int
scala> htn (30)
res7: Int = 32
Der Compiler kann bei endrekursiven Funktionen diese optimieren und einen Stackoverflow vermeiden. Das Schlüsselwort @tailrec weist den Compiler an, eine Fehlermeldung auszugeben, sollte es nicht endrekursiv sein.
Interessant, das wusste ich gar nicht. Aber Scala ist als funktionale Programmiersprache natürlich auf Rekursion hin optimiert. In meinem Video hatte ich eher "old school"-Programmiersprachen wie z.B. C/C++ im Kopf, bei denen die Programme bei zu großer Rekursionstiefe einfach "unfreundlich" abschmieren. :)
@@Gogol-Doering Das ist m.W. keine Frage des Alters, aber (ohne Gewähr, nicht überprüft!) Lisp sollte das ähnlich handhaben - mag aber auch sein, dass bei neueren Lispversionen verschiedene Features erst dazukamen, d.h. ein Test mit einem aktuellen Lisp würde auch keine Gewähr dafür bieten, dass das schon 1970 bei Lisp so war. :)
Hab in meinLispscript geschaut und racket(drracket angeworfen:
(define (htn n)
(if (= n 32)
n
(htn (- n 1))
)
)
(htn 30)
Läuft ewig (> 1h). Statt die Doku zu lesen mach ich lieber ein rasches, schmutziges Experiment. Scheint, als seien Integers nicht Größenlimitiert, zumindest nicht zu einer 32-bit-Größe, sonst wär's in 60 min wohl fertig geworden. Aber auch kein Stacküberlauf.