Problem mit Rekursion



  • Hallo Leute, zu allererst ich besuche dieses Forum auch täglich und stelle auch öfter fragen, da ich zu faul war mein pw zu ändern hab ich mich meist unregistriert gemeldet (als user89 :D).

    Ich wollte fragen ob auch ich hier einen kleinen Frage-Thread haben darf.
    Klar jetzt könnte jeder daherkommen (da es das schon gibt) trotzdem bitte ich um die Erlaubniss.
    Ich poste meist eh nur wenn ich zuvor selber alles probiert habe.

    Hier mal ne Verständnisfrage:

    aus einem (meiner Meinung nach geilem)C-Tut : http://www2.pmf.fh-goettingen.de/~isimon/Informatik/PronixCKurs/ckurs132.html

    Kann mir hier jmd die rekursive Lösung für die Bildung eines ggt erklären?

    Die iterative habe ich ohne probleme verstanden.

    Edit: Hier der konkrete Quellcode:

    *Download:ggt.c*/
    
    #include <stdio.h>
    #define ulong unsigned long
    
    ulong ggt(ulong a, ulong b)
    {
     if(a==b)
        return a;
     else if(a<b)
        return ggt(a,b-a);
     else
        return ggt(a-b,b);
    }
    
    int main()
    {
     ulong a,b;
     printf("ggt = grösster gemeinsamer Teiler\n");
     printf("Zahl 1: ");
     scanf("%lu",&a);
     printf("Zahl 2: ");
     scanf("%lu",&b);
    
     printf("Der ggT von %lu und %lu ist %lu\n",a,b,ggt(a,b));
     return 0;
    }
    

    Vielen Dank



  • Nehmen wir mal a > b: Wenn a durch ggT(a,b) teilbar ist und b durch ggT(a,b) teilbar ist, dann muß auch (a-b) durch ggT(a,b) teilbar sein.

    Warum?

    Es gibt ja die natürlichen Zahlen n, m, mit denen gilt: n*ggT(a,b) = a und m*ggT(a,b) = b. Dann ist a-b = ggt(a,b) (n-m), wobei n-m natürlich wieder eine ganze Zahl ist.

    So wird das Problem stückweise reduziert, das ist der klassische euklidische Algorithmus.



  • bei der rekursiven loesung verwandeln sich deine schleifenvariablen zu parametern der funktion. guck dir beides mal an. die abfolge ist gleich.
    genau aus diesem grund funktionieren lisps (wie z.b. scheme) ohne explizite iterative konstrukte. rekursion wird zu iteration optimiert, indem der stack einfach nicht waechst, wenn die aufrufende funktion den rueckgabewert der aufgerufenen funktion gleich sofort zurueckgibt.

    ganz nach http://de.wikipedia.org/wiki/Euklidischer_Algorithmus

    14, 63 # die groessere der beiden zahlen wird immer um die kleinere vermindert, bis beide gleich sind
    14, 49
    14, 35
    14, 21
    14, 7
    7, 7
    -> 7



  • Hier noch ein schönes Exemplar der rekursiven Variante

    int ggt(int a, int b)
    {
        if ( b > a)
            return ggt( b, a);
        return b != 0 ? ggt( b, a%b) : a;
    }
    

    Die Funktion ruft sich solange b!= 0 ist selber auf (Rekursion).
    Unsichtbar mit von der Partie ist der mächtige Kellerautomat, der
    dabei den Stack aufrollt und anschliessend (zurückspult) den Stack wieder in den Anfangszustand bringt.

    🙂



  • Danke für die Antworten, ich kannte den eukl. Algo nicht daher die Verwirrung 😃


Anmelden zum Antworten