Rekursion

Viele Probleme lassen sich durch einen Algorithmus lösen, der das Problem in viele Teilprobleme zerteilt, die der selben Natur sind.

Aus den Teillösungen wird die Lösung des Problems ermittelt.

Beispiel: Größte gemeinsame Teiler (ggt)

#include <iostream.h>

extern "C" 
{
        #include <stdlib.h> // for atoi(), exit()
}

int ggt(int a, int b) 
{
        if ( b == 0 )
                return(a);
        else
                return(ggt(b, a%b));
}

int main(int argc, char *argv[])
{
        int num1, num2, erg;

        if (argc != 3) 
        {
                cerr << "Usage: " << argv[0] << " number1 number2" <<endl;
                exit(1);
        }
        num1 = atoi(argv[1]);   num2 = atoi(argv[2]);
        if ((!num1) && (!num2)) 
        {
                cerr << argv[0] << ": Der größte gemeinsame Teiler von "
                         << "0, 0 ist nicht definiert" << endl;
                exit(1);
        }
        erg = ggt(num1, num2);
        cout << argv[0] << ": Der größte gemeinsame Teiler von "
                 << num1 << ", " << num2 << " ist: " << erg << endl;
        return 0;
}

Compilatiom

g++ -g -o ggt ggt.cc

Verwendung

ggt 2970 1265

55

Aufgabenstellung: Untersuchen Sie die Funktion ggt() mit dem Debugger!