Endrekursion

[BlackSalad]

Hey, also mir wird nicht wirklich klar woran ich erkenne, dass eine linear rekursive Funktion endrekursiv ost oder nicht.


Der formale Satz finde ich überall, aber nicht so wirklich woran ich es genau sehe an dieser Funktion:

public class ggTklassisch {
	
	public static void main(String[] args){
		int a=Integer.parseInt(args[0]);
		int b=Integer.parseInt(args[1]);
		
		System.out.println(ggT(a, b));
	}

	static long ggT(int a , int b){
		
		if(a>b){
			return ggT(a-b,b);
		}
		else if (a<b){
			return ggT(a, b-a);
		}
		else {
			return a;
		}
	}
	
	
}

Diese ist endrekursiv, aber warum?


Zum Vergleich: Diese ist nicht endrekursiv: Aber warum?

public class FakultaetRekursiv {
	

	public static void main(String[] args){
		
	int n=Integer.parseInt(args[0]);
	
	System.out.println(FunktionRekursiv(n));
	}
	
	static long FunktionRekursiv (int n) {
		if (n==1){
			return 1;
		}
		else {
			return n*FunktionRekursiv(n-1);
		
		}
		
	}
	
	
}

Der formale Satz lautet:

Eine funktion f heißt endrekursiv, wenn der rekursive Funktionsaufruf stets die letzte Aktion des Zweigs zur Berechnung von f ist.
Was der rekursive Funktionsaufruf ist, ist mir klar. Allerdings ist mir nicht klar was mit "Zweig" gemeint ist..
Ich blick da nicht so durch.


Würd mich über ne Erklärung sehr freuen

Danke schonmaL!

 

[darekkay]

Hast du dir auch die Beispiele auf Wikipedia angeschaut?

Zu deinen Beispielen - vergleiche die return-Anweisungen
1.) return ggT(...) bzw. return a
2.) return n*func(...)

Was muss sich die 1. Funktion denn alles "merken"? Muss sie sich überhaupt etwas merken? Und was muss sich die zweite Funktion merken?

Und was passiert, wenn die jeweilige Funktion das letzte mal aufgerufen wird? Erhälst du dann SOFORT das Ergebnis, oder muss mit dem Ergebnis noch weitergerechnet werden? Das sollte in etwa der Unterschied sein

 

[bygones]

Eine funktion f heißt endrekursiv, wenn der rekursive Funktionsaufruf stets die letzte Aktion des Zweigs zur Berechnung von f ist.

wenn du die rekursive funktion aufloesen wuerdest, wuerde dir dir rekursive funktion n*n-1*n-2*....
d.h. die letzte aktion ist die summierung/das produkt der Variable.

bei einem endrekursiven aufruf ist die letzte aktion der letzte rekursive aufruf.

So in etwa - gibt bestimmt wer der das offizieller angeben kann.

 

[Dekker]

Wir reden bei der Rekursion bildlich gesprochen gerne von Bäumen. Such einfach mal nach Rekursionsbaum bei Google und schau dir einige Beispiele an.

Ansonsten stimmt es schon was die Leute hier geschrieben haben. Bei der Endrekursion steht das Endergebnis im letzten rekursiven Aufruf (der auch als Blatt eines Rekursionsbaumes aufgefasst werden kann, da er keine "Kinder" mehr hat) fest und wird sozusagen nur nach oben durchgereicht. Bei der Fakultätsberechnung wird vor dem return noch einmal n_x * n_x-1 berechnet, sprich der Funktionsaufruf ist in diesem Falle nicht die letzte Aktion, um mal bei deiner Definition zu bleiben.

 

[BlackSalad]

Okay danke euch allen

Ich habs jetzt verstanden.

Es liegt alles an dem n* bei der Fakultätsfunktion.


Danke!

 

[BlackSalad]

Hey, ich versuche gerade die Fakultätsfunktion oben in eine endrekursive Version umzuwandeln. Irgendwie klappt es nicht.

Hat jemand eine Idee wo mein Denkfehler liegt? Ich will diese Rekursion endlich verstehen -.-

public class FakultätEndrekursiv {

	public static void main(String [] args){
		int n = Integer.parseInt(args[0]);
		
		System.out.println(hilfsfunktion(n));
	}
	
	static int hilfsfunktion(int n){
		return funktion(n,n-1);
	}
	
	static int funktion(int n, int m){
		if (m==1){
			return 1;
		}
		else {
			return funktion(n*m, m-1);
		}
	}
	
}

 

[bygones]

n ist dein ergebnis, das musst du bei m==1 zurueckgeben, nicht 1