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); // <---------- HIER

    In 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 von x und y ja nicht. (dazu müsstest du mit Pointern oder Referenzen arbeiten). Wenn du x = 2 und y = 3 hast, soll ja beim Rechnen von x + y auch 5 herauskommen, danach aber trotzdem x 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 springen

    Ich 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?


Log in to reply