Diskussion:Rekursive Programmierung

rekursiv / iterativ

"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 08:32, 9. Mai 2006 (CEST)

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) 10:16, 19. Nov. 2010 (CET))

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 20:12, 7. Dez. 2010 (CET)

Meiner Meinung nach kann man doch die Ackermannfunktion nicht komplett iterativ gestalten - sollte ich mich irren? --elTom ^Diskussion 17:57, 1. Dez. 2008 (CET)

die ackermannfunktion ist μ-rekursiv, also gibt es ein aequivalentes WHILE-Programm. [1] --Mario d 13:45, 14. Mai 2013 (CEST)

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) 15:16, 16. Mai 2013 (CEST)

lob / kritik

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) 10:43, 1. Jul. 2005 (CEST))

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

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 08:32, 9. Mai 2006 (CEST)

Fehler in der Einleitung

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 19:00, 6. Apr. 2009 (CEST)

Logischer Fehler?!

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 13:31, 20. Feb. 2008 (CET)

ja stimmt eigentlich - habs ausgebessert. Danke für den Hinweis. --BambooBeast 09:24, 1. Apr. 2008 (CEST)

Defekter Link

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 15:22, 23. Jun. 2010 (CEST)

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 01:00, 22. Aug. 2010 (CEST)

Unqualifizierte Aussagen zur Effizienz

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) 14:54, 24. Mai 2011 (CEST))

Ich bin auch dieser Meinung! Bitte ändern. (nicht signierter Beitrag von 160.85.122.30 (Diskussion) 14:43, 5. Jun. 2013 (CEST))

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) 12:43, 22. Aug. 2013 (CEST))

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) 16:46, 22. Aug. 2013 (CEST)

"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) 21:08, 10. Sep. 2013 (CEST))

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) 21:42, 10. Sep. 2013 (CEST)

Simultane Rekursionen

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 19:19, 6. Jun. 2021 (CEST)

Binäre Suche

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 16:19, 15. Jun. 2021 (CEST)