# endrekursion und lineare rekursion



## BlackSalad (1. Jun 2011)

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 (1. Jun 2011)

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.




			
				Wikipedia hat gesagt.:
			
		

> 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.






BlackSalad hat gesagt.:


> 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 (1. Jun 2011)

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 (1. Jun 2011)

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)
> 
> ...



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 (1. Jun 2011)

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.


----------

