Diskussion:Endrekursion

Ältere Diskussionen

Zur Verallgemeinerung

Die iterative Umformung ist

 while R(x) do
   x := r(x)
 f := s(x)

m Beispiel oben ist r(x)=x+1 und s(x)=x. Aber für R brauch man noch einen Zaähler... tja.

---

Zu

Diese Funktion lässt sich auch iterativ berechnen:

 x := 0
 while n>0 do
   x := x+n
 sum := x+0

Fehlt hier nicht in der while-Schleife ein

   n := n-1

?

---

Die rekursive Definition von Sum(n) war streng genommen nicht endrekursiv, da die Summenoperation (+) effektiv die letzte Operation war und nicht die Rekursion selbst.

Das nun gewählte Beispiel ist wirklich endrekursiv.

---

Verzeiht meine Interaktion, aber das momentan angezeigte Beispiel ist garantiert nicht Endrekursiv, denn wie der Vorredner angedeutet hat ist die letze Operation das (+). Wo ist denn jetzt das 'nun gewählte Beispiel' auf das sich mein Vorredner bezieht? Es müsste doch etwas in dieser Art sein:

 sum(n)
  if n=0
     return 0
  else
     return sum (0, n)

 sum(n,m)
  if m=0 
    return n
  else
    n=n+m
    return sum (n, sum(m-1))
    

Das wäre ECHT Endrekursiv! Die erste sum(n) besteht nur noch damit der Benutzer sie 'wie gewohnt' anwenden kann. Es muss verstanden werden, dass eine Rekursion nicht zu einer Endrekursion wird, wenn der Rekursionsaufruf vermeintlich am Schluss steht. Eine Rekursion wird zur Endrekursion, wenn die letzte Aktion vor dem Return der Rekursionsaufruf ist.

Damit die iterative Funktion der Endrekursiven ähnlich wird schlage ich noch zusätzlich folgende Änderung vor:

  sum(n)
    m := 0
    
    while (n > 0) do
      m   := m + n
      n   := n - 1
    end-while
    return m

Ich werde diese Programme so in den Artikel einfügen, falls kein Widerspruch stattfindet!

Ach übrigens ist das Wort 'effizient' ein extrem umfassendes Wort! Ein Endrekursiver Algorithmus ist in jedem Falle effizienter (Was den Platzbedarf angeht), als ein nicht Endrekursiver Algorithmus! (Sofern die Programmiersprache denn auch mitmacht) Ob ein Endrekursiver Algorithmus effizienter zu warten ist als eine Iteration, kann ich so nicht sagen! Ob Endrekursiv, oder iterativ, beide Algorithmen sind sicher ineffizient gegenüber der 'direkten' Berechnung.

Also wo ist jetzt die Endrekursion explizit so extrem ineffizient?

OK, habs so eingepflegt, und auch gleich noch einige Fehler von mir ausgemerzt... Sorry für die Mehrfachbearbeitungen.

head recursion

Bei Infinitiver Regress steht auch was von head recursion .. .. was ist denn nun richtig ?

Endständige Rekursion

Endrekursion = Endständige Rekursion? --Abdull 16:27, 15. Mär 2006 (CET)

Umwandlung Rekursion <-> Iteration

Zitat: Natürlich kann auch eine endrekursive Funktion, wie jede rekursive Funktion in eine Iteration überführt werden

So natürlich finde ich das gar nicht - kann erklärt werden, wie das bei jeder Funktion klappen soll? --Abdull 16:47, 15. Mär 2006 (CET)

---

Ja, das kann erklärt werden, jedoch hat das nichts mit dem speziellen Thema der END-Rekursion zu tun. Dieser Umstand müsste bei der allgemeinen Rekursion beschrieben sein / werden.

(In Kürze und informal erklärt: Alles was berechenbar ist, ist Turingberechenbar. Da ein rekursiver Algorithmus eine berechenbare Funktion darstellt, kann das auch von einer Turingmaschine berechnet werden. Jede Turingmaschine kann in ein while-Programm, also in ein iteratives Programm umgewandelt werden)

---

Hmmm, ich vermute aber dass das enstehende iterative Programm dann explizit einen Stack verwaltet, da der Rekursionsstack jetzt simmuliert wird (somit ist die Platzkomplexität die des rekursiven Programms. Unter iterativ verstehe ich aber intuitive konstante Platzkomplexität).

Schaecsn 07:32, 30. Dez. 2007 (CET)

O-Notation

Habe bloss noch die O-Notation verlinkt... Leider ist die Seite der O-Notation (Landau-Symbole) für Laien überhaupt nicht verständlich gestaltet! So bringt der Link eigentlich überhaupt nichts, denn der, der die Notation kennt klickt sie nicht an. Hätte jemand noch Power die zu 'entschärfen'?! Vielleicht eine kleine Tabelle mit den gebräuchlisten einfügen?

Ich persönlich empfinde die letzten Änderungen dieser Seite (!die nach mir gemacht wurden!) wirklich als Bereicherung! Weiter so, Jungs und Mädels!!