Die Implementierung von Scheme ist endrekursiv
Kategorie Allgemein Scheme
Also Scheme hat eine endrekursive Implementierung!
Da staunt man was
ich auch nicht
schlecht
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
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
| Permalink | 
Kommentare
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
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
P.P.S.: ich wünsche Dir noch einen schönen Urlaub mit Deiner Familie
Erstellt von Sebastian Stricker um 09:47:56 PM am 03/31/2010 | - Website - |
ich muß ja auch hier nicht was erklären, was schon in Wikipedia steht
Gruß JJR
Erstellt von JakeJBlues um 09:56:09 PM am 03/31/2010 | - Website - |