Einfache Rekursion
-
Hallo,
Ich habe folgende Aufgabe bekommen:if y=0 then x if y>0 then f(x-1, y-1) else f(x+1, y+1)
Wenn ich das richtig verstehe, sollte so Rekursiv die Differenz zwischen x und y berechnet werden. Ist zwar aufwendig, dient aber dem Lernzweck.
Und so sieht mein Code in c++ aus:// Rekursion.cpp #include <iostream> using namespace std; //------------------- definition of functions ----------------------- int rek(int x, int y) { // TODO: implementation if (y == 0) return x; if (y > 0) rek(x - 1, y - 1); else if (y < 0) return rek(x + 1, y + 1); } //---------------------- main()-function ---------------------------- int main() { // test rek int x = 0, y = 0; cout << "Input x: "; cin >> x; cout << "\nInput y: "; cin >> y; rek(x, y); cout << "x is: " << x; return 0; }
Wenn ich Schritt für Schritt durchgehe, geht bis y = 0 alles gut und sollte dann doch eigentlich x zurückgegeben werden. Aber irgendwie wird dann y wieder auf 1 oder -1 gesetzt und das Programm zählt wieder bis zum eigentlichen Wert von y bzw x zurück und gibt dann sozusagen die Eingabe wieder aus. Übersehe ich was?
-
Du hast ein(1) return vergessen.
-
Stimmt, aber das hatte ich schonmal drin. Hatte ich nur gerade bearbeitet und wohl versehentlich gelöscht. Wenn ich das mit rein schreibe, funktionierts aber dennoch nicht
-
@dsenst sagte in Einfache Rekursion:
Stimmt, aber das hatte ich schonmal drin. Hatte ich nur gerade bearbeitet und wohl versehentlich gelöscht. Wenn ich das mit rein schreibe, funktionierts aber dennoch nicht
Das ganze Returnen nützt nichts, wenn du den Wert in main ignorierst.
-
Ich gehe den Code im Debugger ja Zeile für Zeile durch und sehe da schon, dass sich y nach 0 noch verändert, was es aber nicht sollte. Ob der Wert dann in der Main ankommt, kann man dann später noch beheben. Aber es funktioniert ja schon in der Funktion nicht
-
???
-
@manni66 sagte in Einfache Rekursion:
???
Beispiel:
x = 1, y = 2
Werte werden in die Funktion übergeben und da y>0 ist, werden x und y um 1 reduziert. Die neuen Variablen sind also
x = 0, y = 1
y ist immernoch >0. Deshalb x und y reduzieren -> x = -1, y = 0
Jetzt müsste der Code abbrechen und in die Main zurückkehren, aber das passiert nicht. Stattdessen werden x und y wieder um 1 erhöht und das solange bis x und y wieder die Ausgangswerte (hier x = 1, y = 2) erreicht haben. Das macht aber für mich gar keinen Sinn. Ich habe da ja nicht mal festgelegt, dass die Funktion an einer anderen Stelle als y = 0 terminiert.
-
@dsenst sagte in Einfache Rekursion:
Jetzt müsste der Code abbrechen
Nein. Da bricht nichts ab. Da 3 Aufrufe von rek werden nacheinander mit return beendet. Das ist Rekursion. Der Fehler ist in main.
-
@dsenst sagte in Einfache Rekursion:
cin >> y;
rek(x, y); // <---------- HIERIn deinem Mail benutzt du den Rückgabewert von
rek
nicht. Die Funktion returnt das Ergebnis und du wirfst es weg.Schreib:
int ergebnis = rek(x, y); cout << "Ergebnis ist: " << ergebnis << '\n';
Dadurch, dass du
f(x, y)
berechnest, ändert sich der Wert vonx
undy
ja nicht. (dazu müsstest du mit Pointern oder Referenzen arbeiten). Wenn dux = 2
undy = 3
hast, soll ja beim Rechnen vonx + y
auch 5 herauskommen, danach aber trotzdemx
weiterhin gleich 2 sein.
-
@wob
Ahh, stimmt. So war das. Danke dir
Ich verstehe da aber noch nicht, warum dann in der Funktion die Parameter einfach wieder bis zum Startwert bei jedem Durchlauf mit 1 addiert werden anstatt einfach wieder zum Startwert zu springen
-
@dsenst sagte in Einfache Rekursion:
@wob
Ahh, stimmt. So war das. Danke dir
Ich verstehe da aber noch nicht, warum dann in der Funktion die Parameter einfach wieder bis zum Startwert bei jedem Durchlauf mit 1 addiert werden anstatt einfach wieder zum Startwert zu springenIch verstehe deine Frage nicht
Vielleicht lautet die Antwort: weil das x und y innerhalb der Funktion andere x und y sind als außerhalb?
Jedenfalls springt da überhaupt nichts zu irgendeinem Startwert. Was soll überhaupt der Startwert sein?