« Auf nach Carolinensiel! | Main| Das Pascalsche Dreieck »

Die Implementierung von Scheme ist endrekursiv

10
Category  
Also Scheme hat eine endrekursive Implementierung!
Da staunt man was ich auch nicht schlecht
Was bedeutet dies??

Also rekursive Funktionen und Methoden sind ja weithin bekannt, was jeder wohl kennt ist die factorial.
Hier ein kleines Beispiel in C#:

int factorial(int n) { return (n==1)?1:(n*factorial(n-1)); }

((Jetzt komm mir bloss keiner mit dass wäre nicht korrekt!!! Ist ja nur ein Beispiel!!! ))

Wenn man die Funktion jetzt mit factorial(Int32.MaxValule) aufruft, läuft man in einen rischtisch Stackoverflow

Man könnte die factorial ja auch so implementieren

int factorial(int n) { return factorialIter(1,1,n); }
int factorialIter(int product, int counter, int maxcounter) { return (counter>maxcounter)?product:factorialIter(product*counter,counter+1,maxcounter); }

Wenn man die neue factorial nun mit Int32.MaxValue als Parameter aufruft, dann --> Rischtisch auch Stackoverflow, da beides rekursive Methode und C# keine "Endrekursive Implementierung" besitzt /* CRASCH */

Sprachen mit einer Endrekursiven Implementierung würden bei dem Parsen des Ausdruckes -> (counter>maxcounter)?product:factorialIter(product*counter,counter+1,maxcounter) merken, dass auf dem Stack nichts mehr gebraucht wird und alles entfernen.
Oder auch anders ausgedrückt, endrekursive Sprachen kommen ohne for, while, do oder ähnlichem aus. Sie sehen Schleifen nur als syntaktischen Zucker an

Gruß JJR
P.S.: Merke nicht alle rekursiv definierten Prozeduren / Methoden müssen unbedingt rekursiv sein
P.P.S.: Scala ist auch endrekursiv


Comments

Gravatar Image1 - Hi Jörg,

danke für diesen guten Artikel! Ich muss sagen ich war etwas schockiert: da war ich nun an einer der für Informatik in Deutschland als besten geltenden Unis (zumindestens damals) und habe auch das ein oder andere Fachbuch gelesen, aber "endrekursiv" hatte ich noch nie gehört. In dem Wikipedia-Artikel habe ich dann sogar verstanden was es bedeutet Emoticon ...und man sollte es tatsächlich kennen!

Viele Grüße,
Sebastian

P.S.: JAX geht klar, ich gebe dir noch den Namen des Hotels durch in dem ich ab dem 02.05. bin... Äppelwoi-Tour-Reloaded 2010 Emoticon
P.P.S.: ich wünsche Dir noch einen schönen Urlaub mit Deiner Familie Emoticon

Gravatar Image2 - Hallo Sebastian,

ich muß ja auch hier nicht was erklären, was schon in Wikipedia steht Emoticon

Gruß JJR

Post A Comment

:-D:-o:-p:-x:-(:-):-\:angry::cool::cry::emb::grin::huh::laugh::lips::rolleyes:;-)

Amazon


Impressum

Firmenname: Peanuts-Soft
Straße Nummer: Biinger Strasse 8
PLZ Ort: 55263 Wackernheim
Telefon: +491772134526
E-Mail: joerg.reck @ peanuts-soft.de
Disclaimer: Peanuts-Soft übernimmt keine Garantie dafür, dass die auf dieser Website bereitgestellten Informationen vollständig, richtig und stets aktuell sind. Dies gilt auch für alle Links, auf die verwiesen wird. Peanuts-Soft ist für die Inhalte, auf die per Link verwiesen wird, nicht verantwortlich. Peanuts-Soft haftet nicht für konkrete, mittelbare und unmittelbare Schäden oder Schäden, die durch fehlende Nutzungsmöglichkeiten, Datenverluste oder entgangene Gewinne – sei es aufgrund der Nichteinhaltung vertraglicher Verpflichtungen, durch Fahrlässigkeit oder eine andere unerlaubte Handlung – im Zusammenhang mit der Nutzung von Dokumenten oder Informationen bzw. der Erbringung von Dienstleistungen entstehen, die auf dieser Web Site zugänglich sind.
Datenschutz: Inhalt und Gestaltung der Internetseiten sind urheberrechtlich geschützt. Eine Vervielfältigung der Seiten oder deren Inhalte bedarf der vorherigen schriftlichen Zustimmung von Peanuts-Soft.


Locations of visitors to this page

Powered By

Domino BlogSphere
Version 3.0.2