Rekursive Funktionen

stromberg76

Hallo,

ich beschäftige mich jetzt seit ein paar Tagen mit C++ und bin bei rekursiven Funktionen angelangt. Kann mir bitte jemand den Ablauf folgender Funktion erklären? Main() verstehe ich noch. Aber der Ablauf der zweiten Funktion ist mir nicht klar. Ich bitte um Hilfe. Schon mal vielen Dank im Voraus.

typedef unsigned short USHORT;
typedef unsigned long ULONG;
ULONG GetPower(USHORT n, USHORT power);
int main()
{
USHORT number, power;
ULONG answer;
cout << "Geben Sie eine Zahl ein: ";
cin >> number;
cout << "Zu welcher Potenz? ";
cin >> power;
answer = GetPower(number,power);
cout << number << " hoch " << power << "ist gleich " <<
answer << endl;

return 0;

}

ULONG GetPower(USHORT n, USHORT power)
{
if(power == 1)
return n;
else
return (n * GetPower(n,power-1));
}

_matze

Die Funktion gibt entweder n zurück bei der Potenz 1, oder sie ruft sich selbst auf (mit Potenz minus 1) und multipliziert dieses Ergebnis mit n. Oder was ist nicht klar? Was eine rekursive Funktion ausmacht, ist ja gerade, dass sie sich selbst aufruft.

Sonst geh die Funktion doch einfach mit dem Debugger durch.

Simon2

Hi,

ich finde, Rekursion begreift man am leichtesten mit einem Zettel und einem Stift ... (aber vielleicht bin ich einfach nur altmodisch)

Vielleicht mal die einfachste rekursive Funktion, die mir einfällt:

void f(int i) {
   if(i>0) f(i-1);
}

... dann sollte man noch durch- und bedenken, dass jeder Aufruf einer Funktion seinen eigenen Satz an lokalen Variablen(inklusive der Argumente und Returnvariablen) hat, dann kann man auch komplexeren rekursiven Funktionen auf die Schliche kommen ...

.. ist allerdings eine Fleißarbeit (bad news für die Faulen, good news für die, die sich für "zu dumm" halten ).

Gruß,

Simon2.

Fellhuhn

ULONG GetPower(USHORT n, USHORT power)
{
    if(power == 1)
     return n;
    else
       return (n * GetPower(n,power-1));
}

Einfach mal auflösen so einen Aufruf. Zum Beispiel für GetPower(2, 4):

GetPower(2, 4) = 2 * GetPower(2, 3)
GetPower(2, 3) = 2 * GetPower(2, 2)
GetPower(2, 2) = 2 * GetPower(2, 1)
GetPower(2, 1) = 2

Dann einsetzen:
GetPower(2, 4) = 2 * 2 * GetPower(2, 2)
GetPower(2, 4) = 2 * 2 * 2 * GetPower(2, 1)
GetPower(2, 4) = 2 * 2 * 2 * 2
GetPower(2, 4) = 16

stromberg76

Vielen Dank für die Antworten!!

Eure Beiträge haben mir sehr geholfen das Problem zu verstehen!!
Besonderen Dank an Fellhuhn!!