Download:
GgTTest3.java

import info1.*;

public class GgTTest3 {



   public static void main (String[] args) {

        System.out.print("Erste Zahl: " );

        int a = Console.in.readInt();

        System.out.print("Zweite Zahl: " );

        int b = Console.in.readInt();

        System.out.println(ggT(a,b));

   }

   public static int ggT(int a, int b){

      if (a==b) return a;

      else

         if (b>a) return ggT(a,b-a);

         else return ggT(b,a-b);

   }

}

Um die Effizienz des einfachen Euklidchen Algorithmus mit seiner erweiterten Varianten zu vergleichen machen wir am besten ein Zahlenbeispiel. Zuerst der einfache Algorithmus:

ggT(144,15) = ggT(15,144-15) = ggT(15,129)
            = ggT(15,129-15) = ggT(15,114)
            = ggT(15,114-15) = ggT(15,99)
            = ggT(15, 99-15) = ggT(84)
            = ggT(15,84-15) = ggT(15,69)
            = ggT(15,69-15) = ggT(15,54);
            = ggT(15,54-15) = ggT(15, 39)
            = ggT(15, 39-15) = ggT(15,24)
            = ggT(15,24-15) = ggT(15,9)
            = ggT(9,15-9) = ggT(9,6)
            = ggT(6,9-6) = ggT(6,3)
            = ggT(3,6-3) = ggT(3,3)
            = 3

Der effizientere erweiterte Euklidsche Algorithmus braucht statt der 13 nur noch 5 Aufrufe der rekursiven Methode:

ggT(144,15) = ggT(15, 144 mod 15) =  ggT(15, 9)
            = ggT(9, 15 mod 9) = ggT(9,6)
            = ggT(6, 9 mod 6) = ggT(6,3)
            = ggT(3, 6 mod 3)= ggT(3,0)
            = 3

Wie groß der Unterschied zwischen den beiden Algorithmen ist, hängt von der Wahl der Zahlen ab. Wie man sich leicht klar machen kann ist der (einfache) Euklidsche Algorithmus in den meisten Fällen effizienter (jeder gelb unterlegte Schritt des erweiterten Algorithmus, kommt auch im einfacheren Algorithmus vor. Im ungünstigsten Fall ist der erweiterte Algorithmus um höchstens einen Aufruf länger (rot markiert) effizienter.
 

Erste Zahl: 32768
Zweite Zahl: 2
Exception in thread "main" java.lang.StackOverflowError
 

Tatsächlich ist die Rekursionstiefe zu groß. Beim Stack handelt es sich um einen Speicherbereich, auf dem die offenen, also noch nicht beendeten Methoden abgelegt werden. Wie wir wissen, wird bei einem rekursiven Abstieg die Methode immer wieder neu aufgerufen und damit, wie wir gerade gelernt haben, auf den Stack gelegt. Beim rekursiven Aufstieg werden sie alle wieder nach und nach vom Stack geholt. Nun kann es passieren, dass beim rekursiven Abstieg der Stack überläuft bevor der Basisfall erreicht ist. Genau das ist bei unserem Beispiel der Fall. Wir sehen, Rekursionen können oft leichter lesbar und effizienter sein, dafür aber den Speicher des Rechners überfordern.