EndRekursion

[EndRekursion]

Tagchen,

ich verstehe nicht so wirklich wann ein Programm EndeRekursiv ist und wann nicht?

Beispiel Harnoi-Türme:

public class HanoiRek {
	private static int count = 1;
	
	static void Tow(String Quelle, String Hilf, String Ziel, int n) {
		
		count++;
		
		if (n == 1) 
			System.out.println ("Bewege Scheibe " + n + " von " + Quelle + " nach " + Ziel);
		else{
			Tow(Quelle, Ziel, Hilf, n-1);
			System.out.println ("Bewege Scheibe " + n + " von " + Quelle + " nach " + Ziel);
			Tow(Hilf, Quelle, Ziel, n-1);
		}
	}

	public static void main (String args []) {
		long start = System.currentTimeMillis();
		
		System.out.println ("Tuerme von Hanoi");
		Tow("Quelle", "Hilfsziel", "Ziel", 20);
		
		long end = System.currentTimeMillis();
		
		long duration = end - start;
		
		System.out.println("Es hat: " + duration/1000 + " Sekunden gedauert!");
		System.out.println("Anzahl der Schritte: " + count);
	}
}

Ist dieses Programm EndeRekursiv? Wenn ja, warum? Wenn nein, warum nicht?

 

[Sesostris]

Der rekursive Algorithmus zur Lösung der Türme von Hanoi ist nicht endrekursiv und zugleich auch ein gutes Beispiel für nicht endrekursive Funktionen. Wenn du die Ausgabe deines Programmes einmal genauer verfolgst, wirst du feststellen, dass der Turm auf Quelle langsam kleiner wird und auf Ziel sich Schritt für Schritt aufbaut. Wenn du die Stäbe und deren Scheiben nach jedem Zug durch Striche o. Ä. visualisierst, sieht man das schön.

Eine rekursive Funktion geht also immer tiefer in die Rekursion und dann diese Rekursionsebenen schrittweise wieder nach oben.
Bei einer Endrekursion würde der Algorithmus zwar auch in die Tiefe gehen, aber es müsste beim "nach oben gehen" nichts mehr gerechnet werden, denn das Ergebnis steht am tiefsten Punkt der Rekursion bereits fest.

 

[EndRekursion]

Das mag mein Hirn noch nicht so ganz begreifen.
Nehmen wir mal das Beispielprogramm aus Wikipedia:

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

Dieses Programm ist Enderekursiv, aber warum?
Nur wegen:

 if n=0 
     return m

???

Kann man jedes rekursive Programm (wie z.B. Hanoi) in ein Enderekursives Programm
umbauen? Weil wenn man das kann, bedeutet das doch, dass man es auch in
ein iteratives Programm umbauen kann oder nicht?

 

[langhaar!]

Endrekursiv bedeutet, dass nach einem rekursivem Aufruf keine weiterer Schritt mehr erfolgt. Das ist eine strukturelle Eigenschaft, die man unmittelbar aus dem Aufbau des Programmes ablesen kann, ohne das Programm überhaupt zu verstehen.

Jedes rekursive Programm lässt sich in eine iteratives umwandeln (da braucht man gar nicht lange überlegen; da Computer auf Maschinensprachebene nicht über Rekursion verfügen, diese aber in Hochsprachen nachgebildet wird, ergibt sich zwangsläufig, dass jede Rekursion durch Iteration nachgebildet werden kann).

 

[Sesostris]

Das Beispiel von Wikipedia ist endrekursiv, weil am Ende wirklich nur noch der rekursive Aufruf steht:

return add_sum (m+n, n-1)

Während beim nicht endrekursiven Algorithmus zum Schluss auch noch die Addition stattfindet:

return n + sum(n-1)

Verständlicher wird es, wenn man sich die einzelnen Schritte ansieht:

sum(3) = 3 + sum(2)
 sum(2) = 2 + sum(1)
  sum(1) = 1 + sum(0)
   sum(0) = 0
  sum(1) = 1 + 0 = 1
 sum(2) = 2 + 1 = 3
sum(3) = 3 + 3 = 6

Durch die Einrückung sieht man hier schön, dass das Programm zuerst maximal tief in die Rekursion geht (bis sum(0)) und dann wieder zurück und dabei die Teilergebnisse aufsummiert.

Bei der endrekursiven Variante sieht das anders aus:

sum(3) = add_sum(0, 3)
       = add_sum(3, 2)
       = add_sum(5, 1)
       = add_sum(6, 0)
       = 6

Man geht wieder maximal tief in die Rekursion (bis add_sum(6, 0)), aber anstatt nun wieder zurückrechnen zu müssen, steht das Ergebnis nun schon fest.

Deine Vermutung, man könne jedes rekursive Programm in ein endrekursives sowie iteratives überführen und umgekehrt, stimmt.

EDIT:

da Computer auf Maschinensprachebene nicht über Rekursion verfügen [...]

Wie kommst du bitte zu dieser Überzeugung?

 

[EndRekursion]

Ok, also der letzte Aufruf ist ein Rekursiver Aufruf ohne das noch weiter Operationen ausgeführt werden?

Das ist doch aber bei dem Hanoi-Programm der Fall:

Tow(Hilf, Quelle, Ziel, n-1);

 

[Sesostris]

Davor findet aber auch ein rekursiver Aufruf statt; du hast also zwei rekursive Aufrufe. Das kann alleine deswegen schon unmöglich endrekursiv sein.

 

[EndRekursion]

Ok, verstanden!

Enderekursiv wenn:

Letzter allein stehender Aufruf ist der rekursive Aufruf mit dem keine Operation mehr durchgeführt wird!

Danke