6.8.9 Der rekursive ggT-Algorithmus (Vers. 3)
 
Noch einmal der erweiterte Euklidsche Algorithmus 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);
}

Schreibtischtest Ein sog. Schreibtischtest kann das Arbeiten der Methode verdeutlichen. Wir wählen dazu drei Szenarien, nämlich die Berechnung von ggT(3,3), also die Berechnung des ggT zweier gleicher Zahlen, den ggT(24,36) als Vertreter eines gängigen Beispiels und schließlich ggT(17,19) als Beispiel für die Berechnung eines ggTs zweier teilerfremden Zahlen, wo wir als ggT-Wert die 1 erwarten.

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.
 

Download:
GgTTest2.java
Das Beispielprogramm zeigt nicht nur das Funktionieren der rekursiven Methode, es macht auch deutlich, dass man die Methode nicht erst in einer Klasse wie Mathematik unterbringen muss um sie zu testen, wir können auch eine Kasse GgTTest2.java schreiben, in der die statische Methode ggT(int a, int b) implementiert ist und von der main-Methode aus aufgerufen wird.
 
 

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!]

  Ausgabe:
erste Zahl: 162019746
zweite Zahl: 115728390
23145678
0.0 Sekunden
 
Bemerkungen Die Methode ggT(...) ist außerhalb der main-Methode implementiert, vergleichbar der Implementierung der Methoden in der Klasse Mathematik. Der Aufruf erfolgt ohne Punktnotation, da die Klasse dort implementiert ist, wo sie auch benutzt wird. Wir haben damit die Methode gleich so geschrieben, dass wir sie ohne Änderungen in die Klasse Mathematik übernehmen können.
 
Bemerkung zur Ausgabe

Download:
Mathematik.java

Hat man sich einmal an rekursive Methode gewöhnt, sind diese häufig einfacher zu implementieren und zu lesen, als nichtrekursive Methoden.1) Da, wie die Ausgabe zeigt, die rekursive Methode gegenüber der letzten Version zur Berechnung des ggT nichts an Effizienz eingebüsst hat, entscheiden wir uns dafür, die 'ältere' Version der ggT-Methode in der Klasse Mathematik durch die neuere, die rekursive zu ersetzen. 
Fußnote  

1)

Es gibt sogar Algorithmen, die man nur rekursiv formulieren kann, für die wir keine nichtrekursive Algorithmen finden können. Beispiel dafür ist der sog. Quicksort-Algorithmus, den wir später noch kennen lernen werden. [zurück]
 
zu 6.8.10 Fakultät n!
zur Startseite www.pohlig.de  (C) MPohlig 2005