13.3 ggT rekursiv definiert

 
Was ist eine rekursive Methode? Wie der euklidche Algorithmus gezeigt hat, wir der ggT zweier Zahlen mittels ggT zweier (einfacherer) Zahlen bestimmt. Fertig sind wir, wenn die Zahlen, deren ggT bestimmt werden soll gleich sind, oder wenn b 0 ist. Schauen wir uns zunächst den Quelltext der rekursiven Methode an:
static int ggT(int a, int b){
   if(a==b||b==0) return a;
   else return ggT(b,a%b);
}
Schreibtischtest Das Beispiel zeigt, wie im Innerhalb einer Methode diese selbst wieder aufgerufen wird. Wie unser rekursive Algorithmus arbeitet, machen wir uns am besten an einem Schreibtischtest klar. Dazu wählen wir jeweils Werte für a und b so, dass man alle Möglichkeiten testet.
Beispiele:

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.
 
  Wichtig ist, dass bei jedem erneuten Aufruf der Methode, die dabei übergebenen Werte immer einfacher werden. Damit das Verfahren terminiert, muss garantiert werden, dass irgendwann eine der beiden Ausstiegsbedingungen, also a==b oder b==0 erfüllt ist.
 
Download GgT4.java 
import info1.*;
public class GgT4{
   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);
   }
}
Bemerkungen Die Methode ggT(...) ist hier 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.
Ergebnis

 
Download:
Mathematik.java

Hat man sich einmal an rekursive Methode gewöhnt, sind sie häufig einfacher zu implementieren und zu lesen, als nichtrekursive Methoden. Da auch die rekursive ggT-Bestimmung für unsere Testzahlen weniger als eine Millisekunden benötigt entscheiden wir uns dafür, die rekursive Methode in unsere Klasse Mathematik aufzunehmen. 

zu den Hausaufgaben  
zur Startseite www.pohlig.de (C) MPohlig 2003