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)

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))

Im Artikel Rekursive Programmierung steht: „Alle rekursiven Algorithmen lassen sich jedoch auch durch iterative Programmierung implementieren“. Vor etlichen Jahren hieß es „Die meisten rekursiven Algorithmen lassen sich ..“. In der Diskussion zum Artikel (erster Diskussionspunkt, ohne Überschrift) wurde dieses Problem behandelt. Die Diskussion bricht 2008 ab mit dem Einwand „Meiner Meinung nach kann man doch die Ackermannfunktion nicht komplett iterativ gestalten“. Ich meine, dass dieser Einwand zu Recht besteht und bitte um Überprüfung. Dann müsste es wieder „die meisten Funktionen“ anstatt „alle Funktionen“ heißen. --Pinguin55 (Diskussion) 22:29, 15. Mai 2013 (CEST)

Völlig korrekt angemerkt, nur die Primitiv-rekursive Funktionen lassen sich iterativ berechnen. Diese Klasse umfasst jedoch nicht alle berechenbaren Funktionen, wie die besagte Ackermannfunktion--Andreschulz (Diskussion) 22:48, 15. Mai 2013 (CEST)

die aussage wundert mich ein bischen, die diskussion dazu sollte aber lieber auf der disk stattfinden. --Mario d 10:24, 16. Mai 2013 (CEST)

Meine vorige Anmerkung ist so nicht richtig ist. Die Ackermann-funktion ist nicht LOOP-Berechenbar, aber 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)