Rekursiver Methodenaufruf

Bestimmung des GGT und kgV

Unter dem Begriff Rekursion versteht man einen Methodenaufruf aus einer Methode welche sich wiederum selbst aufruft bis eine bestimmte Bedingung eintritt. Eine Rekursion stellt somit eine alternative Möglichkeit zu einer Schleife dar.

Im folgenden Beispiel wird anhand eines rekursiven Methodenaufrufes der GGT (größter gemeinsamer Teiler) zweier Zahlen nach dem Algorithmus von Euklid bestimmt. Ist der GGT gefunden, kann das kgV (kleinstes gemeinsames Vielfache) durch die Formel kgV = (zahl1*zahl2)/GGT leicht ermittelt werden.

Mit dem Algorithmus wird mit Hilfe des Modulo Operanden % der Rest zweier ganzer Zahlen ermittelt. Zahl1 erhält nun den Wert von Zahl2 und Zahl2 erhält den Wert des Restes. Diese Schritte werden solange wiederholt, bis der Rest = 0 ist.

 

Beispiel:

Zahl1 = 486, Zahl2 = 42

486 % 42 Rest = 24
42 % 24 Rest = 18
24 % 18 Rest = 6
6 % 0 GGT = 6

 

namespace ConsoleApplication_ggt_kgv
{
    class Program
    {
        static void Main(string[] args)
        {
            int zahl1, zahl2;

            Console.WriteLine("Dieses Programm berechnet den GGT und das kgV zweier Zahlen");
            Console.WriteLine("===========================================================\n");

            Console.Write("1. Zahl? ");
            zahl1 = Convert.ToInt32(Console.ReadLine());
            Console.Write("2. Zahl? ");
            zahl2 = Convert.ToInt32(Console.ReadLine());

            int GGT = Function_GGT(zahl1,zahl2);
            Console.WriteLine("\nGGT = " + GGT);

            int kgV = Function_kgV(zahl1,zahl2);
            Console.WriteLine("kgV = " + kgV);

            Console.ReadLine();
        }
        
        static int Function_GGT(int zahl1, int zahl2)
        {
            if (zahl2 == 0)
                return zahl1;   // Wenn zahl2 == 0 wurde der GGT gefunden
            else
            {
                return Function_GGT(zahl2, zahl1 % zahl2);    // rekursiver Methodenaufruf
            }
        }

        static int Function_kgV(int zahl1, int zahl2)
        {
            int ggt = Function_GGT(zahl1,zahl2);    // zuerst GGT ermitteln
            int kgv = (zahl1 * zahl2) / ggt;        // kgv = (zahl1 * zahl2)/GGT
            return kgv;
        }
    }
}

 

GGT und kgV in C#