Rekursion

FunkyJustice · 03/31/2017, 00:45

Hallo,

ich hätte eine Frage zur Rekursion, angenommen diese Funktion ist gegeben:

Code:

public static int gcd(int p, int q){
		 while (q!=0) {
			 int old_q = q;
			 q = p % q;
			 p = old_q; 
		 }      
		 return p;  }

Diese soll Rekursive dargestellt werden. Mein Ansatz wäre:

Code:

 public static int gcdre(int p, int q){
		if(q==0){
			return p; }
		return gcdre(p, q%p); }

und wenn man auf ein if/while/for verzichten möchte:

Code:

 public static int gcd(int p, int q){
			return (q==0) ? p : gcd(p, q%p); }

Bei kleinen Zahlen bringt mir mein Ansatz ein richtiges Ergebnis, aber bei größeren Zahlen ein java.lang.StackOverflowError. Wie könnte man dies besser lösen?

(Entschuldigt bitte diese banale Frage, ich bin noch Anfänger und dies ist ein Klausur relevantes Thema für mich.

Mikesch01 · 03/31/2017, 03:31

Müsste der Rekursionscode nicht so lauten?

Code:

public static int gcdre(int p, int q){
		if(q==0){
			return p; }
		return gcdre(q, p%q); 
}

Man beachte die Parameter beim return in Zeile 4

florian0 · 03/31/2017, 11:28

Quote:

Originally Posted by Mikesch01

Müsste der Rekursionscode nicht so lauten?

Richtig. Sieht man ja auch an der Schleife

Code:

public static int gcd(int p, int q){
		 while (q!=0) {
			 int old_q = q;
			 q = p % q;
			 p = old_q; 
		 }      
		 return p;  }

Das q wird zum neuen p.

(Ein Fehler den ich in den Übungen sehr oft sehe

)

Exo · 04/22/2017, 01:55

Just don't use Java xD

Afair Java doesn't support tail recursion optimization (more time and larger stack). So for larger numbers you should use an algorithm as Lehmer's algorithm (very efficient).