nicht angemeldet Michael_K
Matti Mäkitalo
Michael_K
Tabellenkalk
Rolf B
Rolf B
Rolf B
Tabellenkalk
Hallo,
das Problem ist bekannt, nur ich weiss nicht, ob es eine Lösung gibt. Eine Funktion ruft sich zu oft selber auf. Das liegt aber nicht an einer Fehlerhaften funktion sondern es muss tatsächlich in hohem Umfang durchlaufen werden. Welche Lösungsmöglichkeit hat man hierfür in Javascript? Auf der Mozilla Seite wird das Problem beschrieben, aber die Lösungen scheinen auf meinen Fall nicht anwendbar. Gibt es eine Quelle, wo man Lösungsansätze nachlesen kann.
VG Michael
Hallo,
jeder rekursive Algorithmus hat ein iteratives Pendant. Iterative Algorithmen haben i.d.R. kleine Callstacks, was dein Problem verhindern wird.
Kannst du uns Beispiel-Code geben, so dass wir dir bei der Umgestaltung helfen können?
VG Matti
Hallo Matti,
anbei ein Code-Beispiel für folgende XML Struktur. Bitte hinterfrage nicht die Sinnhaftigkeit der XML Struktur, die kann ich nicht beeinflussen. Das Problem entsteht, wenn eine große Anzahl von <line/> mit einander via id-Attribute verbunden sind. Wenn mehr als ca. 8000 line verknüpfte vorliegen, kommt es zur Meldung too much recursion.
<line id="a35" nextLine="a45"/>
<line id="a78" nextLine="a88"/>
<line id="a45" nextLine="a78"/>
<line id="a88"/>
const getAllLines = function(startLine){
let idList = [];
const _loop = function(line){
if(line.hasAttribute('id')) idList .push(line.getAttribute('id'));
if(line.hasAttribute('nextLine')) {
const nextID = line.getAttribute('nextLine');
const nextLine = document.getElementById(nextID );
if(!idList.includes(nextID) && nextLine) _loop(nextLine);
}
}
// beginne mit der Startlinie
_loop(startLine);
}
Gruß Michael
Hallo,
Wenn mehr als ca. 8000 line verknüpfte vorliegen, kommt es zur Meldung too much recursion.
im ersten Posting hast du noch von hohem Umfang geschrieben. Jetzt nur 8000?
Wenn ich deinen Code richtig verstehe, gehst du einerseits zeilenweise vor, andrerseits sammelst du zusätzlich rekursiv alle verlinkten Zeilen zusätzlich ein. Möglicherweise moppeldoppelst du da was?
Gruß
Kalk
Hallo Michael,
das Durchlaufen einer einfach verketteten Liste ist Teil von "Algorithmen und Datenstrukturen - Einsteigerstufe" und lässt sich sehr einfach mit einer while-Schleife erledigen. Ohne Rekursion.
Das kriegst Du bestimmt hin.
Rolf
<line id="a35" nextLine="a45"/> <line id="a78" nextLine="a88"/> <line id="a45" nextLine="a78"/> <line id="a88"/>
Jedes Element kann nur einmal vorkommen und kann auch nur einen Nachfolger haben. Das ist eine schnurgerade Liste, da sehe ich den Nutzen einer Rekursion nicht. Fehlt irgendeine Information?
const getAllLines = function(line) {
let idList = [];
while (line) {
if (line.hasAttribute('id')) {
idList.push(line.getAttribute('id'));
}
if (line.hasAttribute('nextLine')) {
let id = line.getAttribute('nextLine');
if (! idList.includes(id)) {
line = document.getElementById(id);
}
else {
line = null;
}
else {
line = null;
}
}
}
Davon unabhängig: Die hasAttribute-Aufrufe könnten eigentlich raus, getAttribute liefert null, falls das Attribut nicht existiert. Anstatt nachzugucken, ob etwas da ist, und es dann abzufragen, kannst du auch direkt abfragen und schauen, ob dabei null rauskommt.
Hallo Radischen,
jetzt hast Du es verpetzt. Ich wollte Michael doch über Weihnachten was zum Nachdenken bescheren.
Aber es fehlt noch ein return idList 😉
Man könnte auch eine Generatorfunktion schreiben, die die Lines in ihrer Reihenfolge liefert. Aber das hängt natürlich von der geplanten Verarbeitung ab.
Rolf
Hallo Michael_K,
die mögliche Rekursionstiefe von JS ist eigentlich ziemlich gewaltig. Um sie zu erhöhen, müsste man per Startparameter die Stacksize der JS Engine verändern, und ich kenne keinen Browser, der das ermöglicht.
Abgesehen von der potenziellen iterativen Lösung, die Matti ansprach, sollte man auf jeden Fall genau hinterfragen, ob Du wirklich keinen Fehler drin hast, der Dich zu tief rekursieren lässt.
Rolf
Hallo Rolf,
siehe meine Antowrt zu Matti mit Code-Beispiel.
Gruß Michael
Hallo,
das Problem ist bekannt, nur ich weiss nicht, ob es eine Lösung gibt. Eine Funktion ruft sich zu oft selber auf. Das liegt aber nicht an einer Fehlerhaften funktion sondern es muss tatsächlich in hohem Umfang durchlaufen werden. Welche Lösungsmöglichkeit hat man hierfür in Javascript? Auf der Mozilla Seite wird das Problem beschrieben, aber die Lösungen scheinen auf meinen Fall nicht anwendbar. Gibt es eine Quelle, wo man Lösungsansätze nachlesen kann.
ich bin noch mittendrin im Prozess, Rekursion zu verstehen, daher nur kurz neugierig nachgefragt, ob sichergestellt ist, dass die Rekursion irgendwann abbricht?
Gruß
Kalk
Hallo Kalk
ich bin noch mittendrin im Prozess, Rekursion zu verstehen, daher nur kurz neugierig nachgefragt, ob sichergestellt ist, dass die Rekursion irgendwann abbricht?
Ja, das ist sichergestellt, da die Anzahl der Rekursionen durch die Anzahl der XML-Elemente in einem Dokument begrenzt ist und sichergestellt wird, dass Elemente nicht doppelt aufgerufen werden. Siehe mein Code-Beispiel in meiner Antwort zu Matti.
Gruß Michael