Problem mit Speicherallokierung in rekursiver Funktion

  • geschlossen
  • C

  • Chais
  • 925 Aufrufe 3 Antworten

Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

  • Problem mit Speicherallokierung in rekursiver Funktion

    Hi
    also ich soll im Zuge eine Programmierpraktikums für die Uni ein prog schreiben, das eine Zahlenfolge ausgibt.
    Dabei sind die ersten beiden Zahlen vorgegebenermaßen 1 und 1
    Die nächste Zahl erhält man nun, indem man die beiden letzten Zahlen nimmt, ihren Wert von der noch leeren Stelle rückwärts zählt, und die dort stehenden Zahlen addiert.
    Also:
    1 1 x
    zweimal 1 rückwärts ergibt jeweils 1, 1+1=2 also x=2
    1 1 2 x
    einmal 2 und einemal 1 rückwärts ergibt 1 und 2, zusammen 3
    1 1 2 3
    und so weiter.

    Iterativ hab ich die aufgabe bereits gelöst. Das Problem is nu dass ich die Aufgabe jetzt rekursiv lösen muss.
    Dabei hab ich Probleme mit dem Speicher, da ich ja einen Array anlegen muss, aber die erforderliche Größe bis zum Start der Funktion nicht bekannt ist. Außerdem habe ich keinen Zugriff auf die verwendete main() nur auf die Subfunktion.
    malloc is schon klar. Das Problem is, ich will den Speicher ja nur beim ersten durchlaufen der Funktion allokieren. Aber sobald ich malloc in eine if-Schleife packe beendet die von mir geschriebene main() schon nach dem einlesen von n. Also der Variablen, die die größe des Arrays angibt.

    C-Quellcode

    1. #include <stdio.h>
    2. #include <stdlib.h>
    4. int *reihe,x=2;
    6. int qRekursiv(int n)
    7. {
    8. if (x==2){
    9. reihe=malloc(sizeof(*reihe)*n);
    10. if (reihe==NULL){
    11. return 0; //Rückgabe im Fehlerfall
    12. }
    13. reihe[0]=1;
    14. reihe[1]=1;
    15. }
    16. reihe[x]=reihe[x-reihe[x-1]]+reihe[x-reihe[x-2]]; //Berechnung der aktuellen Zahl
    17. printf("%4i", reihe[x]); //Trace zum beobachten der Berechnung
    18. if (x==n-1){
    19. return reihe[x]; //Rückgabe des gewünschen Ergebnisses
    20. }
    21. x++; //Weiter zählen
    22. qRekursiv(n);
    23. }
    25. int main()
    26. {
    27. int n,q;
    28. printf("Geben sie ein n ein: ");
    29. scanf("%i", &n); //Einlesen der Größe
    30. q=qRekursiv(n);
    31. if (q==0){ //Reaktion auf Speichermangel
    32. printf("Der Speicher reicht nicht aus, um eine so grosse Zahl zu berechnen.");
    33. return 1;
    34. }
    35. printf("\nDie %i-te Q-Zahl lautet: %i", n, q);
    36. return 0;
    37. }
    Alles anzeigen

    Speziell bei diesem Beispiel wird die Berechnung zwar durchgeführt und ist auch richtig, aber der Rückgabewert ist trotzedem 0... warum auch immer...
    Wenn ich malloc nicht in die if-Schleifen packe, wird natürlich bei jedem Durchlauf der Speicher neu allokiert und mein Ergbnis lautet 0.
    Momentan habe ich also die Wahl zwischen: Array bei jedem Durchlauf löschen, Funktion garnicht erst starten und korrekt Rechnen aber fälschlicherweise 0 bekommen oO...
    Hoffe ihr könnt mir helfen. Ich hab nicht den blassesten Schimmer was ich noch versuchen könnte.

    greetz Chais

    Dieser Beitrag wurde bereits 4 mal editiert, zuletzt von Chais ()

  • Probiers mal mit "return qRekursiv(n);" anstatt nur "qRekursiv(n);". ;)
    Denn mit qRekursiv(n) rufst du ja nur eine Funktion auf, die evtl. etwas zurueck gibt. Aber dadurch gibst du ja selber in dem Moment nix zurueck.

    Chais schrieb:

    Wenn ich malloc nicht in d[en] if-[Block] packe, wird natürlich bei jedem Durchlauf der Speicher neu allokiert

    Noe, dafuer steht ja "if (x == 2)" da und im naechsten Durchgang ist x ja eins mehr.


    Allerdings funzt es natuerlich nicht fuer n = 1 und n = 2.
    Und dann waers denk ich mal natuerlich noch gut, wenn man die Funktion mehr als ein Mal verwenden koennte. ^^

    C-Quellcode

    1. #include <stdio.h>
    2. #include <stdlib.h>
    6. int qRekursiv(int n) {
    7. int *reihe;
    8. int result;
    9. reihe=malloc(sizeof(int)*n);
    10. if (reihe==NULL){
    11. return 0; //Rückgabe im Fehlerfall
    12. }
    13. reihe[0]=1;
    14. reihe[1]=1;
    16. result = qIntern(n,1,reihe);
    17. free(reihe);
    18. return result;
    19. }
    21. int qIntern(int n, int x, int* reihe) {
    22. if (x == n) {
    23. return reihe[n-1]; //Rückgabe des gewünschen Ergebnisses
    24. }
    26. x++; //Weiter zählen
    27. reihe[x] = reihe[x-reihe[x-1]] + reihe[x-reihe[x-2]]; //Berechnung der aktuellen Zahl
    29. return qIntern(n,x,reihe);
    30. }
    32. int main() {
    33. int n,q;
    34. printf("Geben sie ein n ein: ");
    35. scanf("%i", &n); //Einlesen der Größe
    36. q=qRekursiv(n);
    37. if (q==0){ //Reaktion auf Speichermangel
    38. printf("Der Speicher reicht nicht aus, um eine so grosse Zahl zu berechnen.");
    39. return 1;
    40. }
    41. printf("\nDie %i-te Q-Zahl lautet: %i", n, q);
    42. return 0;
    43. }
    Alles anzeigen
    Wo ist der Discord Server

    Dieser Beitrag wurde bereits 5 mal editiert, zuletzt von Skyte ()

  • hrhr
    ja den einfall die allokierung vin qRekursiv machen zu lassen und die eigentliche Berechnung in ne weitere Funktion zu packen hatte ich auch schon. aber dann meckert mich die Prüfumgebung an, dass ich qRekursiv rekursiv implementieren soll. und da ich keinen zugriff auf die main() habe, kann ich auch nix an den Parametern ändern, die qRekursiv übergeben werden. Auch die Allokierung kann ich nich auslagern.
    Wie gesagt, momentan rechnet die Funktion richtig, gibt aber aus irgend einem Grund 0 zurück. Hab auch schon versucht, ob ich einfach ne for-Schleife einbaue, und die bei jedem Durchlauf eins weiter zählen lasse. Hat aber aer nich geklappt.
    Aber ich danke dr für deine Hilfe Skyte :D

    greetz Chais

  • Ok, ist eigentlich logisch, du brauchst das hier:

    C-Quellcode

    1. #include <stdio.h>
    2. #include <stdlib.h>
    6. int qRekursiv(int n) {
    7. if (n == 1 || n == 2) return 1;
    9. return qRekursiv(n-qRekursiv(n-1)) + qRekursiv(n-qRekursiv(n-2));
    10. }
    13. int main() {
    14. int n,q;
    15. printf("Geben sie ein n ein: ");
    16. scanf("%i", &n); //Einlesen der Größe
    17. q=qRekursiv(n);
    18. if (q==0){ //Reaktion auf Speichermangel
    19. printf("Der Speicher reicht nicht aus, um eine so grosse Zahl zu berechnen.");
    20. return 1;
    21. }
    22. printf("\nDie %i-te Q-Zahl lautet: %i", n, q);
    23. return 0;
    24. }
    Alles anzeigen
    Wo ist der Discord Server

    Dieser Beitrag wurde bereits 4 mal editiert, zuletzt von Skyte ()