Rekursion

03/31/2017 00:45 FunkyJustice#1

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.

03/31/2017 03:31 Mikesch01#2

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

03/31/2017 11:28 florian0#3

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 :p)

04/22/2017 01:55 Exo#4

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