Rekursionsdurchläufe mit if anweisung einmal zu viel

mimus

Hallo,

ich lern grad c++ und hab a hoch b mittels rekursion zu lösen.
Wenn ich in der unterfunktion rekursion die else anweisung ausklammere macht das programm einen durchlauf zu viel also : 2 hoch 2 = 8. Ist der else-zweig dabei so kommt das richtig ergebnis raus ( 2 hoch 2 = 4). Das verstehe ich nicht und hoffe, dass mir hier geholfen wird.

hier mein quellcode mit else:

#include <iostream>
#include <cmath>
#include <iomanip>
#pragma hdrstop
#include <conio>

using namespace std;

#pragma argsused

int rekursion (int x, int y);

int main(void)
{
 int a, b, erg;
 cout << "Gib zwei zahlen ein [a b]" << endl;
 cin >> a >> b;

 erg = rekursion(a, b);
 cout << "a hoch b = " << erg << endl;

 getchar();
 return 0;
}

 int rekursion (int x, int y)
 {
     if (y)
     {
        x = x * rekursion (x, y-1);
     }
     else
     {
        x = 1;
     }
     return x;
 }

wenn man also else { x = 1;} ausklammert funktionierts nicht

vielen dank

Bashar

Wieso verstehst du das nicht? Wenn du die Funktion geschrieben hast, musst du doch wissen, wozu dieser Zweig gut ist.

mimus

ich hab halt rum probiert...
der zweig ist nur da um a hoch 0 abzufangen, denn sonst stürzt das programm ab, ich verstehe nicht wieso das aber auch einfluss auf die anzahl der durchläufe der if anweisung hat.

Bashar

Nö, ohne den Zweig kommt a^0 = a raus. Probieren ist ja ganz nett, aber man sollte immer wissen, was man tut. Lösch die Funktion und überleg dir von vorn, wie man die Potenz rekursiv definieren kann.

1. Wie sieht der Basisfall aus?
2. Wie reduziere ich einen komplexeren Fall auf einen einfacheren?

mimus

Ja, aber mir gehts ums prizip, ich möchte gern verstehen warum, wenn man den else- zweig löscht bei einer eingabe von 2 hoch 2 als ergebnis 8 rauskommt und wenn der else- zweig dabei ist eben 4.
Denn der else-zweig sollte doch keinen einfluss auf die wiederholung der if anweisung haben???

Wenn ich mir irgendeine andere lösung überlege, verstehe ich ja das problem mit der if anweisung trotzdem nicht, und wenn später ähnliche dinge gebraucht werden, die komplexer sind find ich dann den fehler nicht...

Dasd

Hat Bashar doch schon geschrieben.

Rechne mal ohne den else-Zweig 2^0, 3^0 usw. aus. Vllt. bemerkst du da etwas.

Bashar

mimus schrieb:

Ja, aber mir gehts ums prizip, ich möchte gern verstehen warum, wenn man den else- zweig löscht bei einer eingabe von 2 hoch 2 als ergebnis 8 rauskommt und wenn der else- zweig dabei ist eben 4.

Du könntest das Programm einfach mal per Hand durchgehen (Papier und Bleistift). Für kleine Zahlen (2^2 oder so) sind das nur wenige Zeilen.

Denn der else-zweig sollte doch keinen einfluss auf die wiederholung der if anweisung haben???

Die if-Anweisung wird doch nicht wiederholt, da ist ja nirgends eine Schleife.

Wenn ich mir irgendeine andere lösung überlege, verstehe ich ja das problem mit der if anweisung trotzdem nicht, und wenn später ähnliche dinge gebraucht werden, die komplexer sind find ich dann den fehler nicht...

Naja, der Sinn meiner amateurpädagogischen Ausführung ist eigentlich, dass du genau dasselbe Programm nochmal schreibst, aber diesmal weißt wieso es funktioniert

knivil

rekursion(2, 2) // da 2 != 0 wird daraus ...
2 * rekursion(2, 1) // da 1 != 0 wird daraus
2 * 2 * rekursion(2, 0) // 0 == 0 also wird der else-Zweig ausgefuehrt und die Rekursion gestoppt, die Rueckgabe ist 1
2 * 2 * 1

Falls der else-Zweig weggelassen wird, ist das zurueckgegebene x nicht 1 sondern gleich dem uebergebenen Parameter, hier 2. Daraus wird dann im letzten Schritt 2 * 2 * 2.

mimus

Danke!

jetzt ist der groschen gefallen,

ich hab mich irgendwie drauf versteift, dass beim rekursiven aufruf der if zweig wiederholt wird, und garnicht dran gedacht, dass ja die gesamte funktion aufgerufen wird und das im letzen durchlauf dann eben mit 1 statt x mulipliziert wird wenn else aktiv ist und somit das richtige ergebnis rauskommt.

vielen dank
und liebe grüße

mimus

hab zu dem thema doch noch ne frage:

int rekursion (int x, int y)
 {

     if (y)
     {
        return x * rekursion (x, y-1);
     }
     else
     {
        x = 1;
        return x;
     }

man kann die rekursion ja auch so umschreiben, aber wo ist dann das ergebnis von

x * rekursion (x, y-1);

gespeichert während die funktion sich immer selbst aufruft?

danke

_matze

Zitier die Zeile doch komplett, dann dürfte es klar sein (=>Rückgabewert).

knivil

man kann die rekursion ja auch so umschreiben, aber wo ist dann das ergebnis von

Es liegt noch nicht vor, da erst der rekursive Ausdruck noch ausgewertet werden muss. Der Sinn von Rekursion ist: Berechne erstmal ein einfacheres Problem und benutze das Ergebnis fuer dein groesseres Problem.