Diskussion:Rekursive Programmierung
rekursiv / iterativ
[Quelltext bearbeiten]"Die meisten rekursiven Algorithmen lassen sich jedoch durch iterative Programmierung implementieren." - Ich war der Meinung, dass das bei _allen_ geht? Blubbalutsch 20:55, 23. Aug 2003 (CEST)
Derselben Meinung bin ich auch, ich sollte es eigentlich auch wissen! Werde das demnächst nochmal sicherstellen und dann gegebenenfalls korrigieren. GGShinobi Diskussion:Rekursive Programmierung#c-GGShinobi-2006-05-09T06:32:00.000Z-rekursiv / iterativ11
- geht bei allen, steht ja im prinzip auch da: den "stack" kann man in jeder programmiersprache simulieren, und über eben diesen mit einer "while-schleife" "drüberlaufen". Oder formal: jede intuitiv berechenbare Funktion ist auch while-berechenbar (Churchsche These, vgl.hierzu zum Beispiel Schöning, Theoretische Informatik kurzgefasst). Das effizienzargument (iterativ ist grundsätzlich schneller als rekursiv) ist mir allerdings gänzlich neu: gibt es da eine quelle für? alex 130.149.17.40 18:54, 6. Aug 2006 (CEST)
- Hat schonmal wer den Algorithmus von Dijsktra iterativ geschrieben? Das ist meiner Meinung nach bis heute nicht möglich. Von daher würde ich der Formulierung "jede intuitiv berechenbare Funktion" eher zustimmen. (nicht signierter Beitrag von 94.220.82.147 (Diskussion) Diskussion:Rekursive Programmierung#c-94.220.82.147-2010-11-19T09:16:00.000Z-GGShinobi-2006-05-09T06:32:00.000Z11)
- geht bei allen, steht ja im prinzip auch da: den "stack" kann man in jeder programmiersprache simulieren, und über eben diesen mit einer "while-schleife" "drüberlaufen". Oder formal: jede intuitiv berechenbare Funktion ist auch while-berechenbar (Churchsche These, vgl.hierzu zum Beispiel Schöning, Theoretische Informatik kurzgefasst). Das effizienzargument (iterativ ist grundsätzlich schneller als rekursiv) ist mir allerdings gänzlich neu: gibt es da eine quelle für? alex 130.149.17.40 18:54, 6. Aug 2006 (CEST)
- Jede, wirklich jede rekursive Funktion ist iterativ umsetzbar - ob das effizient ist oder nicht, spielt für die Betrachtung der Machbarkeit keine Rolle. Wäre das nicht möglich, so könnten bestimmte rekursive Funktionen gar nicht ausgeführt werden: der (oder die) Prozessor macht ja keine Magie, die eine Hochsprache nicht nachbilden kann, sondern arbeitet auch nur mit einem Stack. Die primitivste (aber in der Regel ineffizienteste) Form der Umwandlung von rekursiven in interative Funktionen ist die Verwendung eines eigenen Stacks in der Hochsprache. Bei bestimmten Algorithmen bleibt auch gar nichts anderes übrig, es so zu machen (wenn man es unbedingt iterativ haben will/muss), das ist aber ineffizienter als den Stack des Prozessors zu nutzen. --Mark Nowiasz Diskussion:Rekursive Programmierung#c-Mark Nowiasz-2010-12-07T19:12:00.000Z-94.220.82.147-2010-11-19T09:16:00.000Z11
- Meiner Meinung nach kann man doch die Ackermannfunktion nicht komplett iterativ gestalten - sollte ich mich irren? --elTom Diskussion Diskussion:Rekursive Programmierung#c-ElTom-2008-12-01T16:57:00.000Z-GGShinobi-2006-05-09T06:32:00.000Z11
- die ackermannfunktion ist μ-rekursiv, also gibt es ein aequivalentes WHILE-Programm. [1] --Mario d Diskussion:Rekursive Programmierung#c-MarioS-2013-05-14T11:45:00.000Z-ElTom-2008-12-01T16:57:00.000Z11
- Meine Anmerkung auf Wikipedia Diskussion:Redaktion Informatik war nicht richtig ist. Die Ackermann-funktion ist nicht LOOP-Berechenbar, aber in der Tat WHILE-Berechenbar - das hatte ich irgendwie im Hinterkopf - hatte es dann aber gestern zu später Stunde in den falschen Zusammenhang gebracht. Da aber WHILE Schleifen bei der iterativen Programmierung zulässig sind, kann man die Ackermannfunktion natürlich iterativ berechnen. Der Satz kann also inhaltlich so stehen bleiben. Sorry für die Verwirrung. --Andreschulz (Diskussion) Diskussion:Rekursive Programmierung#c-Andreschulz-2013-05-16T13:16:00.000Z-GGShinobi-2006-05-09T06:32:00.000Z11
lob / kritik
[Quelltext bearbeiten]Fakultät wird zwar gerne als Beispiel benutzt, würde man besser anders implementieren. Bäume sind bessere Beispiel. Just my 2cent. Softeis 17:39, 4. Mär 2004 (CET)
Ein GANZ DICKES KOMPLIMENT an den/die Autor(en) dieser Seite!!!!
Studiere E-Technik 2. Semester. In Informatik sind wir gerade bei rekursiver Programmierung. Weder in der Vorlesung, noch in einschlägigen Büchern wird das Thema so gut erklärt wie hier. Für mich als Anfänger hat es wirklich weiter geholfen ,auch das mit der Fakultät. (nicht signierter Beitrag von 217.249.125.179 (Diskussion) Diskussion:Rekursive Programmierung#c-217.249.125.179-2005-07-01T08:43:00.000Z-lob / kritik11)
- für dich als anfänger: "ein mops kam in die küche und stahl dem koch ein ei./ da nahm der koch das messer und schlug den mops entzwei. / da kamen viele möpse und gruben ihm ein grab. / drauf setzten sie 'nen grabstein, auf dem geschrieben stand: ein mops kam in die küche und stahl dem koch ein ei./ da nahm der koch das ....."(Deutsches Liedgut), klassisches Beispiel einer endlosen Rekursion, weil niemand eine Abbruchbeding hinzugefügt hat. Jedes Kind kapiert das, nur an der Uni muss man das höchstkompliziert vermitteln :-/ nun ja, vielleicht hilft es dir weiter. ob das im artikel was verloren hat, kann und mag ich jetzt nicht beurteilen... alex 130.149.17.40 18:54, 6. Aug 2006 (CEST)
Bestehender Artikel "Rekursion": Zusammenführung
[Quelltext bearbeiten]Ich habe grade entdeckt, das es 2 Artikel zu dem Thema Rekursion gibt. Ausser diesem hier noch "Rekursion". Ich bin für eine Zusammenführung der Artikel, weiß allerdings (noch) nicht wie das geht. Ich werde mich, wenn keine Einwände kommen, demnächst darum kümmern. :-) GGShinobi Diskussion:Rekursive Programmierung#c-GGShinobi-2006-05-09T06:32:00.000Z-Bestehender Artikel "Rekursion": Zusammenführung11
Fehler in der Einleitung
[Quelltext bearbeiten]Die rekursive Programmierung findet oft Anwendung in prozeduralen und objektorientierten Programmiersprachen. Obwohl diese Sprachen in ihrem Sprachstandard die Rekursion ausdrücklich zulassen, stellen Selbstaufrufe und gegenseitige Aufrufe bei der Programmierung die Ausnahme dar. Die meisten Programme in diesen Sprachen sind rein iterativ.
Das ist doch ein Widerspruch in sich. Wie kann die rekursive Programmierung oft in prozeduralen und objektorientierten Sprachen zur Anwendung kommen, wenn Selbstaufrufe, also Rekursion!, die Ausnahme sind? Ich ändere das jetzt mal. --DrumsInVitro Diskussion:Rekursive Programmierung#c-DrumsInVitro-2009-04-06T17:00:00.000Z-Fehler in der Einleitung11
Logischer Fehler?!
[Quelltext bearbeiten]Im Text steht:
Mit der Startzahl x=4 würde der Computer rechnen:
fac(4*fac(3*fac(2*fac(1))))
heraus kommt dann das richtige Ergebnis, nämlich 24.
Müsste es beim Beispiel nicht
fac(4*fac(3*fac(2*fac(1*fac(0)))))
heissen? Schließlich greift der Abbruch erst bei "x=0"
82.82.176.184 Diskussion:Rekursive Programmierung#c-82.82.176.184-2008-02-20T12:31:00.000Z-Logischer Fehler?!11
- ja stimmt eigentlich - habs ausgebessert. Danke für den Hinweis. --BambooBeast Diskussion:Rekursive Programmierung#c-BambooBeast-2008-04-01T07:24:00.000Z-82.82.176.184-2008-02-20T12:31:00.000Z11
Defekter Link
[Quelltext bearbeiten]der link "Einführung und Beispiele in C++" mit dem Ziel "http://tutorial.schornboeck.net/rekursion.htm" führt auf eine nicht vorhandende Seite. Ich weiß nicht was ich damit machen soll. Vielleicht kennt einer diese Seite und kann den Link ändern oder einfach entfernen. --Patrickobs Diskussion:Rekursive Programmierung#c-Patrickobs-2010-06-23T13:22:00.000Z-Defekter Link11
Ich hab den Original-Link auskommentiert, und einen Link zu Archive.org gesetzt. Falls mal jemand feststellt, dass der Originallink wieder funktioniert, bitte wiederherstellen! -- Sotel Diskussion:Rekursive Programmierung#c-Sotel-2010-08-21T23:00:00.000Z-Defekter Link11
Unqualifizierte Aussagen zur Effizienz
[Quelltext bearbeiten]Der Abschnitt zur Effizienz ist in seiner allgemeinen Formulierung schlicht falsch, da sich die Aussagen nur auf einige wenige Programmiersprachen beziehen, die keinerlei Optimierungen auf Rekursion vornehmen. Selbst ältere C-Compiler sind da aber schon wesentlich weiter, sodass zumindest Endrekursion in der Performance vollkommen identisch zu Schleifenkonstrukten ist (dafür aber oftmals einfacher zu verstehen...).
Mein Vorschläg wäre, die Aussagen zur Effizienz vollständig zu streichen und sich darauf zu beschränken, dass jeder rekursive Algorithmus iterativ und jeder iterative Algorithmus rekursiv umgesetzt werden kann (siehe dazu auch oben). Sprach- und Compiler-abhängige Effizienz ist einfach nicht sinnvoll dokumentierbar, wenn man über ein solch allgemeines Konzept spricht. (nicht signierter Beitrag von 137.226.194.56 (Diskussion) Diskussion:Rekursive Programmierung#c-137.226.194.56-2011-05-24T12:54:00.000Z-Unqualifizierte Aussagen zur Effizienz11)
Ich bin auch dieser Meinung! Bitte ändern. (nicht signierter Beitrag von 160.85.122.30 (Diskussion) Diskussion:Rekursive Programmierung#c-160.85.122.30-2013-06-05T12:43:00.000Z-Unqualifizierte Aussagen zur Effizienz11)
Zu sagen, "Rekursive Programme haben in der Regel keine gute Performance." ist ein Kategorienfehler - Das was vom Rechner ausgeführt wird ist schliesslich der Maschinencode. Wenn man unbedingt will kann man schreiben: Rekursiver Code wird von vielen Compilern (oft) zu ineffizientem Maschinencode umgesetzt. Auch diese Aussage ist allerdings nicht fachgerecht - bis zu einem gewissen Grad ist es immer so, dass höhere Sprachelemente teilweise von Compilern ineffizient umgesetzt werden. Man sagt schliesslich auch nicht "WHILE Programme sind in der Regel ineffizient" und begründet dieses Statement damit, dass "Assembler Code in gewissen Fällen bessere Performance als WHILE Programme (eigentlich von einem Compiler aus einem While Programm generierten Assembler/Maschinen Code) habe". (nicht signierter Beitrag von 160.85.104.70 (Diskussion) Diskussion:Rekursive Programmierung#c-160.85.104.70-2013-08-22T10:43:00.000Z-Unqualifizierte Aussagen zur Effizienz11)
- Nein, weder das eine noch das andere.
- Allein der Umstand, dass Compiler versuchen Rekursionen wegzuoptimieren, indiziert mehr als deutlich, dass Rekursionen ineffizient sind. Was dazu führt, ist im Text beschrieben und ist auch nichts Compiler-spezifisches. --Plankton314 (Diskussion) Diskussion:Rekursive Programmierung#c-Plankton314-2013-08-22T14:46:00.000Z-160.85.104.70-2013-08-22T10:43:00.000Z11
- "Allein der Umstand, dass Compiler versuchen Rekursionen wegzuoptimieren, indiziert mehr als deutlich, dass Rekursionen ineffizient sind." Diese Aussage ist völlig sinnfrei, der compiler hat gar keine Wahl die Rekursion nicht "wegzuoptimieren" oder kennst du vielleicht einen Prozessortyp der nativ Rekursion unterstützt? Zu deiner Information sei noch angemerkt, dass der Compiler auch WHILE-Schleifen "wegoptimiert" d.h. in Sprungbefehle übersetzt was aber nicht "indiziert"(induziert?), dass Schleifen böse oder ineffizient sind. Wichtig ist aber, dass verschiedene Compiler rekursive aufrufe auf verschiedene Arten "übersetzen", einige produzieren nun mal in gewissen Fällen (z.B. Endrekursio/tail-recursion) performanteren Maschinencode. (nicht signierter Beitrag von 91.190.10.183 (Diskussion) Diskussion:Rekursive Programmierung#c-91.190.10.183-2013-09-10T19:08:00.000Z-Plankton314-2013-08-22T14:46:00.000Z11)
- Jeder Prozessortyp unterstützt "nativ" Rekursionen, solange er nur in der Lage ist, Sprünge im Programm auszuführen bzw. Funktionsaufrufe zu tätigen.
- Schleifen sind, wie Rekursionen, je nach Prozessor und Länge ebenfalls ineffizient. Das ist der Grund weswegen auch sie (teilweise) wegoptimiert werden.
- Außerdem ist es dem Compiler - entgegen deiner Behauptung - nicht immer möglich, Rekursionen wegzuoptimieren.--Plankton314 (Diskussion) Diskussion:Rekursive Programmierung#c-Plankton314-2013-09-10T19:42:00.000Z-91.190.10.183-2013-09-10T19:08:00.000Z11
- "Allein der Umstand, dass Compiler versuchen Rekursionen wegzuoptimieren, indiziert mehr als deutlich, dass Rekursionen ineffizient sind." Diese Aussage ist völlig sinnfrei, der compiler hat gar keine Wahl die Rekursion nicht "wegzuoptimieren" oder kennst du vielleicht einen Prozessortyp der nativ Rekursion unterstützt? Zu deiner Information sei noch angemerkt, dass der Compiler auch WHILE-Schleifen "wegoptimiert" d.h. in Sprungbefehle übersetzt was aber nicht "indiziert"(induziert?), dass Schleifen böse oder ineffizient sind. Wichtig ist aber, dass verschiedene Compiler rekursive aufrufe auf verschiedene Arten "übersetzen", einige produzieren nun mal in gewissen Fällen (z.B. Endrekursio/tail-recursion) performanteren Maschinencode. (nicht signierter Beitrag von 91.190.10.183 (Diskussion) Diskussion:Rekursive Programmierung#c-91.190.10.183-2013-09-10T19:08:00.000Z-Plankton314-2013-08-22T14:46:00.000Z11)
Simultane Rekursionen
[Quelltext bearbeiten]Ich weiß zwar nicht ob es etwas für den Artikel beitragen kann, weil es aktuell für Wikipedia noch unter "Theoriefindung" fallen würde, aber ich beschäftige mich seit dem Jahr 2008 sehr intensiv mit Sortierverfahren. 2008 hatte ich versucht Quicksort in einer Basic-Programmiersprache zum Laufen zu bringen, die keine Rekursionen unterstützt. Ich habe dies dann jedoch mit simultanen Rekursionen doch geschafft. Simultane Rekursionen sind technisch genau das gleiche wie normale Rekursionen, weil sie exakt das gleiche machen und auf die gleiche Art und Weise funktionieren, nur mit einem ganz entscheidenden Unterschied: Sie führen keine Selbstaufrufe aus und können daher in fast allen Programmiersprachen und auf allen Systemen umgesetzt werden. So zum Beispiel auch in Basic, auf den alten Commodore-Computern, wie dem C64.
Wie funktioniert das?
Wenn ein Algorithmus zum Beispiel am Ende erst die linke und dann die rechte Hälfte seines Arbeitsbereiches als neue Rekursionen starten muss, dann wird die rechte (!) Hälfte durch ihre Start-Werte an ein Rekursions-Array angehängt und dann springt der Programmablauf mit den linken Start-Werten einfach zum Anfang des Codes. Und wenn die Bedingung für den Start weiterer Rekursionen nicht gegeben ist, dann werden die Start-Werte vom Ende des Rekursions-Arrays abgeholt, der letzte Datensatz im Rekursions-Array gelöscht und der Programmablauf springt wieder zum Anfang des Codes. Wenn das Rekursions-Array leer ist, dann ist der Arbeitsablauf beendet.
Hinweis: Ein Rekursions-Array ist nichts weiter als ein herkömmliches Array, das dann in seinen Datensätzen die Werte enthält, die an die einzelnen Rekursionen übergeben werden.
Verdeutlichung der Funktionsweise
Ein simultanrekursives Sortierverfahren sortiert ein Array mit 1000 Werten (0 - 999). Die aktuell aktive simultane Rekursion (s.R.) arbeitet im Array im Bereich 250 bis 374. Wenn nun die Bedingung für eine weitere Teilung in einen linken und rechten Bereich gegeben ist, dann werden die rechten Werte 312 (links) und 374 (rechts) als ein Datensatz an das Rekursions-Array angehängt und der Algorithmus springt mit den linken Werten 250 (links) und 311 (rechts) zum Anfang seines Codes.
Vorteile:
Simultane Rekursionen arbeiten grundsätzlich immer ganz erheblich schneller als echte Rekursionen und sie benötigen auch deutlich weniger Systemressourcen.
Risiko Stapelüberlauf nicht gegeben
Bei einigen Sortierverfahren sind echte Rekursionen nur eingeschränkt nutzbar. Wenn man zum Beispiel vom originalen Bubblesort die rekursive Version in Excel mit Visual Basic testet, dann kommt es ab 5000 zu sortierenden Werten / Datensätzen unweigerlich zu einem Stapelüberlauf. Bei simultanen Rekursionen kann dies nicht passieren. Vorausgesetzt natürlich, das Rekursions-Array wurde ausreichend groß dimensioniert.
Gruß von Martin Oppermann (Gifhorn / Niedersachen) --77.21.163.85 Diskussion:Rekursive Programmierung#c-77.21.163.85-2021-06-06T17:19:00.000Z-Simultane Rekursionen11
Binäre Suche
[Quelltext bearbeiten]Muss das wirklich in den Artikel? Man kann das zwar so programmieren, aber das macht doch in der Praxis absolut keinen Sinn, weil der Programmieraufwand und Speicherverbrauch viel zu groß ist und weil die Suche dann ganz erheblich langsamer läuft. Die reine binäre Suche an sich, hat außerdem nichts mit der rekursiven Programmierung zu tun. 5 Zeilen Programmcode, mehr ist das nicht.
Pseudocode:
do
p=[[Mitte aus Anfang und Ende]]
if [[Bedingung: Anfang soll sein Mitte]] then Anfang = p
if [[Bedingung: Ende soll sein Mitte]] then Ende = p
loop until Anfang=Ende
--77.21.163.85 Diskussion:Rekursive Programmierung#c-77.21.163.85-2021-06-15T14:19:00.000Z-Binäre Suche11