Warum funktioniert diese rekursion nicht?



  • Hallo,

    mit dem folgenden Minimalbeispiel gibt es einen speicherzugriffsfehler.
    Mir ist nicht ganz klar warum. Ich laufe rekursiv durch und eigentlich lege ich doch mit *pm in der signatur einen pointer an der auf den pointer der vorherigen rekursion zeigt. warum klappt das nicht? Könnte es sein dass ich
    bei der abbruchbedingung dann (für den fall i = 4) ****pm schreiben müsste?
    Ich würde mich über genaue Aufklärung sehr freuen! Danke

    #include <iostream>
    
    void foo(int* pm, int i)
    {
            std::cout << "It: " << i << std::endl;
            if (i == 0) 
            {
                *pm = 3;
                return;
            }
            foo(pm,i-1);
    }
    
    int main()
    {
        int *m = NULL;
        foo(m,4);
        std::cout << "ENDE: " << *m << std::endl;
    }
    


  • *pm = 3;

    denk mal nach auf welchen Speicher pm zeigt.



  • *pm = 3 liegt auf dem stack. ich bin mir nicht sicher - kann es sein dass pro rekursion ein eigener stack angelegt wird - wohl ja. heißt dass dann das *pm = 3 auf dem "innersten" stack liegt ? dieser danach nicht mehr verfügbar ist?



  • Matse schrieb:

    *pm = 3 liegt auf dem stack. ich bin mir nicht sicher - kann es sein dass pro rekursion ein eigener stack angelegt wird - wohl ja. heißt dass dann das *pm = 3 auf dem "innersten" stack liegt ? dieser danach nicht mehr verfügbar ist?

    nein, vergiss die rekursion.
    was passiert hier:

    int main() {
      int* p=NULL;
      *p=3;
    }
    

    ?

    und vergleiche das mit:

    int main() {
      int i;
      int* p=&i;
      *p=3;
    }
    


  • m zeigt auf 0

    Matse schrieb:

    int *m = NULL;
        foo(m,4);
    

    Hier würde es auf das Objekt m vom Typ int zeigen welches auf dem Stack liegt:

    int m = 0;
    foo(&m, 4);
    


  • Shade Of Mine schrieb:

    Matse schrieb:

    *pm = 3 liegt auf dem stack. ich bin mir nicht sicher - kann es sein dass pro rekursion ein eigener stack angelegt wird - wohl ja. heißt dass dann das *pm = 3 auf dem "innersten" stack liegt ? dieser danach nicht mehr verfügbar ist?

    nein, vergiss die rekursion.
    was passiert hier:

    int main() {
      int* p=NULL;
      *p=3;
    }
    

    ?

    und vergleiche das mit:

    int main() {
      int i;
      int* p=&i;
      *p=3;
    }
    

    also korrigiert mich bitte: beim ersten dereferenziere ich einen nicht zugewiesenen pointer oder? Das ist nicht erlaubt oder? deswgen der speicherzugriffsfehler ?
    für mein ausgangsproblem läuft er bis nach unten druch und dereferenziert er auch hier einen nicht zugewiesenen pointer?


  • Mod

    Matse schrieb:

    für mein ausgangsproblem läuft er bis nach unten druch und dereferenziert er auch hier einen nicht zugewiesenen pointer?

    Auch. Aber der Fehler funktioniert schon früher. Ich werde die Funktion mal inline machen und die Rekursion durch eine äquivalente Schleife ersetzen:

    #include <iostream>
    
    int main()
    {
        int *m = NULL;
    
        for(int i=4;;--i)
        {
         std::cout << "It: " << i << std::endl;
         if (i == 0)
          {
            *m = 3;
             break;
          }
        }
    
        std::cout << "ENDE: " << *m << std::endl;
    }
    

    Dieser Code ist 1:1 äquivalent zu deinem Beispielprogramm. Fällt dir vielleicht jetzt etwas auf?



  • Matse schrieb:

    also korrigiert mich bitte: beim ersten dereferenziere ich einen nicht zugewiesenen pointer oder?

    Der Zeiger ist schon initialisiert, nämlich mit NULL . Nullzeiger dereferenzieren darf man nicht.

    Matse schrieb:

    für mein ausgangsproblem läuft er bis nach unten druch und dereferenziert er auch hier einen nicht zugewiesenen pointer?

    Er (wer eigentlich?) dereferenziert wie gesagt einen Nullzeiger.

    Nicht zugewiesen/nicht initialisiert wäre sowas:

    int* ptr; // zeigt irgendwo hin
    *ptr = 3; // !
    

    Das ist ebenso verboten. Meistens sieht es sogar noch schlimmer aus als bei Nullzeigern, da der Fehler von Laufzeitumgebungen schlecht erkannt werden kann. Du hast dann typisches undefiniertes Verhalten. Wenn du Pech hast, läuft das Programm ungehindert weiter, überschreibt irgendwelche Daten und produziert nicht nachvollziehbare Fehler.



  • SeppJ schrieb:

    Matse schrieb:

    für mein ausgangsproblem läuft er bis nach unten druch und dereferenziert er auch hier einen nicht zugewiesenen pointer?

    Auch. Aber der Fehler funktioniert schon früher. Ich werde die Funktion mal inline machen und die Rekursion durch eine äquivalente Schleife ersetzen:

    #include <iostream>
    
    int main()
    {
        int *m = NULL;
    
        for(int i=4;;--i)
        {
         std::cout << "It: " << i << std::endl;
         if (i == 0)
          {
            *m = 3;
             break;
          }
        }
    
        std::cout << "ENDE: " << *m << std::endl;
    }
    

    Dieser Code ist 1:1 äquivalent zu deinem Beispielprogramm. Fällt dir vielleicht jetzt etwas auf?

    also ich steh jetzt auf dem schlauch...
    so wie ich das sehe geht ja schon das hier nicht:

    int main()
    {
        int *m = NULL;
    
       *m = 3;
        std::cout << "ENDE: " << *m << std::endl;
    }
    

    nur warum? Ich lege einen pointer auf einen int an - also eine speicherzelle die halt nicht existiert - das ist doch der fehler oder nicht? Also dass ich nicht auf eine variable zeige !? oder bin ich jetzt blöd?



  • Nein, das stimmt schon. Der Zeiger zeigt auf Null und somit auf keinen gültigen Speicher. Folglich darfst du ihn nicht dereferenzieren, weil du dann auf den Speicherbereich dahinter zugreifen würdest.

    Hast du meinen vorherigen Beitrag noch gesehen? 😉



  • ah verstehe - danke nexus. das war also schon die antwort. also hat mein problem nix mit rekursion zu tun sondern einfach was mit falscher dereferenzierung.



  • Matse schrieb:

    Ich lege einen pointer auf einen int an - also eine speicherzelle die halt nicht existiert - das ist doch der fehler oder nicht? Also dass ich nicht auf eine variable zeige !? oder bin ich jetzt blöd?

    Du deklarierst einen Zeiger. Dieser ist default-initialisiert zeigt also "irgendwo hin". Dieses "irgendwo" ist das Problem, denn an der Stelle wird wohl kein passendes Objekt liegen.
    Es gibt jetzt zwei Möglichkeiten:
    * Der Zeiger zeigt auf ein dynamisch erzsugtes Objekt
    * Der Zeiger zeigt auf ein Objekt auf dem Stack.
    Ersteres musst du manuell wieder freigeben, zweiteres wird automatisch freigegeben (also zerstört).
    Das Problem ist nun dass der Zeiger, wird er verwendet, auf etwa korrektes zeigen MUSS, sonst gibt das Speicherzugriffsfehler oder undefiniertes verhalten.
    Und wenn du einen unintialisierten Zeiger an eine Funttion übergibst die erwartet dass hinter dem Zeiger ein Objekt steht (also der Zeiger auf was konkretes zeigt), schaffst du dir Probleme - dein Programm macht nicht das was du willst, im besten Falle stürzt es (reprodutierbar) ab.


Log in to reply