endrekursion und lineare rekursion

[BlackSalad]

Hey,

ich verstehe die Enrekursion nicht so wirklich.
Ich check auch nicht ganz wofür das gut sein soll, wenn es sowieso langsamer ist als interativ.

Naja. es will nicht ganz in meinen Kopf wie das funktionieren soll.
zum Beispiel hab ich hier nen Code mal aus meinem Skript genommen, der ein Beispiel für ne endrekursion sein soll:

static int ggT2(int a, int b) {
if (b == 0) {
return a;
} else {
return ggT2(b, a % b);
}
}

ich weiß, dass der rekursive Funktionsaufruf die letzte Aktion des Zweigs zur Berechnung von der fuktion sein muss. Aber was bedeutet das in der Realität?


Ich würd mich freuen, wenn mir das jemand mal anschaulich erklären könnte. Hab schon ewig gesucht, aber versteh es immer noch nicht. :noe:


Danke schonma

 

[chalkbag]

Was mir nicht klar ist, verstehst du Rekursion an sich nicht, oder weißt du nur nicht was eine Endrekursion ist. Aus deinem Text deuten Anzeichen auf beides.

Eine rekursive Funktion f ist endrekursiv (englisch: tail recursive) (auch endständig rekursiv, iterativ rekursiv, repetitiv rekursiv), wenn der rekursive Funktionsaufruf die letzte Aktion zur Berechnung von f ist.[1] Vorteil dieser Funktionsdefinition ist, dass kein zusätzlicher Platz zur Verwaltung der Rekursion benötigt wird.

ich weiß, dass der rekursive Funktionsaufruf die letzte Aktion des Zweigs zur Berechnung von der fuktion sein muss. Aber was bedeutet das in der Realität?

Der Vorteil, oder was das bedeutet, ist dass du eben nicht die Methode aufrufst und das Ergebnis nochmal separat betrachten musst. Anders gesagt, eine Endrekursion ist iterativ eine While-Schleife -> also mit Abbruchbedingung.
Vielleicht hilft es dir unterschiedliche Formen der Rekursion zu betrachten und so den Unterschied zu verstehen? (Rekursion ? Wikipedia)
Vielleicht hilft dir aber auch folgender Link, unter welchem die Unterscheide endrekursiv und nicht-endrekursiv behandelt werden (Rekursion)

 

[BlackSalad]

also ich glaube die rekursion an sich verstanjden zu haben, zumindest im groben, bin mir aber sehr unsicher. da mir das mit dem werte zurückgeben nicht so ganz klar ist wie das das funktioniert.

Aber bei der Endrekursion blick ich gar nicht durch...

 

[chalkbag]

aus meinem Link von Oben

Lineare Rekursion

Eine Funktion ist linear rekursiv, wenn nur ein rekursiver Aufruf erfolgt. Für die Fakultätsfunktion könnte das so aussehen:
fakul 0 = 1
fakul n = n(fakul n-1)

Der Computer würde bei Aufruf fakul 3 im ersten Schritt alle Aufrufe auf den Stack legen:
1. fakul 3 = 3 *
2. ( 2 *
4. ( 1 *
5. ( 1 ) ) )

und nach erreichen des Rekursionsankers fakul 0 = 1 alle auf dem Stack abgelegten Zahlen aufmultiplizieren:
5. ( 1 ) ) )
6. ( 1 *
7. ( 2 *
8. 3 *
9. 6 =

Die Rekursion wird also einmal hin und zurück durchlaufen.

Lineare Rekursionen, die nicht noch einmal "zurücklaufen", nennt man endrekursiv (tail recursion). Man unterscheidet also zwischen endrekursiven und nicht-endrekursiven linearen Rekursionen. Die Fakultätsfunktion lässt sich auch endrekursiv implementieren:
fakul 0 a = a
fakul n a = fakul (n-1) (a*n)

Besser könnt ich es nicht erklären, mir hat beim verstehen der Rekursion geholfen, das ganze mal für ein echtes Beispiel (z.b. dein ggt) auf dem Papier Schritt für Schritt zu durchlaufen.

 

[BlackSalad]

Danke schonmal. Ich glaub ich weiß jetzt schon bisschen mehr 🙂


Wäre das dann bei meinem Beispiel so, dass a und b gegeben sein müssen. und beim beispiel 6 und 4
würde die Funktion dann..

erst schauen, ob b 0 entspricht. und feststellen, dass b nicht 0 entspricht.

if (4 == 0) {

dann quasi ggT2(4, 6 % 4) nach oben geben

return ggT2(4, 6 % 4);



dann wäre quasi nach einem durchgang ggT2(4,6) ggT2(ggT2 6, 6% 4)


oder wie?

und wie wäre dann der 2. durchlauf?


Also mit der Fakultät ist es mir irgendwie deutlicher wie das geht. Aber bei dem ggT hab ich ja garkein n. Also keinen Basisfall.