Schauen wir uns noch einmal den erweiterten Euklidschen Algorithmus an, so wie wir in 12.5 kennen gelernt haben. Ob wir den ggT(792,75) oder den ggT(75,42) berechnen ist gleich, wir landen immer bei ggT(6,3) und damit bei 3. Das bedeutet aber nichts anderes, dass wir bei jedem Vorrücken um eine Zeile nach unten die Berechnung eines ggT zweier Zahlen durch die Berechnung des ggT einfacherer Zahlen ersetzen. Damit haben wir eine rekursive Formulierung der Berechnung des ggT zweier Zahlen. Wie einfaches Nachrechnen zeigt, ersetzen wir beim Zeilenwechsel die Berechnung von

ggT(a,b) durch ggT(b,a mod b)

wobei a mod b wieder der Rest bei der Division a/b ist. Das alte b wird demnach zum a im nächsten Durchgang und das der Rest (a mod b) wird zum b des nächsten Schritts. Damit der rekursive Abstieg sich nicht im 'unendlichen' verliert, benötigen wir eine Abbruchbedingung, den Basisfall. Den haben wir erreicht, wenn a und b gleich sind, oder wenn b = 0 ist. Der erste Fall tritt eigentlich nur ein, wenn von Anfang an, der ggT zweier gleicher Zahlen bestimmt werden soll. Der Normalfall ist durch die Abbruchbedingung b = 0 ist. Wir sehen das an der letzten Zeile unseres obigen Beispiels. Hier hat a den Wert 6, b den Wert 3 und der Rest (a mod b) ist 0. Da noch keine Abbruchbedingung erfüllt ist kommt es zu dem nächsten Aufruf zur Berechnung des ggTs durch ggT(b, a mod b). Für den nächsten Durchgang ist der erste Parameter (jetzt a) 3 und der zweite 6 mod 3 und damit 0. Die Annruchbedingung ist erreicht, denn der zweite Parameter (jetzt b) ist 0. Der Wert des gesuchten ggT, nämlich 3 ist in a gespeichert, weshalb wir diesen zurückmelden. Eine Javamethode, die den rekursiven Algorithmus implementiert sieht dann so aus:

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


ggT(3,3) =* 3

ggT(24,36) =* ggT(36,24 mod 36) = ggT(36,24) =* ggT(24,36 mod 24) = ggT(24,12) =*ggT(12,24 mod 12) = ggT(12,0) =* 12

ggT(17,19) =* ggT(19, 17 mod 19) = ggT(19,17) =* ggT(17,19 mod 17) = ggT(17,2) =* ggT(2, 17 mod 2) = ggT(2,1) =* ggT(1, 2 mod 1) 0 ggT(1,0) =* 1
[Anmerkung: '*=' ist eine Umformung auf Grund eines rekursiven Aufrufs, die anderen '='-Zeichen sind lediglich algebraische Umformungen, denn der Rechner wertet z.B. ggT(2,17 mod 2) direkt zu ggT(2,1) aus.
 

import info1.*;
public class GgTTEst2{
   public static void main(String[] args){
      StoppUhr eineStoppUhr = new StoppUhr();
      int ggT = 1;
      System.out.print("erste Zahl: ");
      int a = Console.in.readInt();
      System.out.print("zweite Zahl: ");
      int b = Console.in.readInt();
      int r;
      eineStoppUhr.starten();
      System.out.println(ggT(a,b));
      eineStoppUhr.stoppen();
      System.out.println(eineStoppUhr);
   }
   static int ggT(int a, int b){
     if(a==b||b==0) return a;
     else return ggT(b,a%b);
   }
}

[Stoppuhr.class muss im aktuellen Verzeichnisliegen!]

Download:
Mathematik.java

¹⁾