Problem mit Speicherallokierung in rekursiver Funktion

[Chais]

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.

#include <stdio.h>
#include <stdlib.h>

int *reihe,x=2;

int qRekursiv(int n)
{
    if (x==2){
        reihe=malloc(sizeof(*reihe)*n);
        if (reihe==NULL){
            return 0;                    //Rückgabe im Fehlerfall
        }
        reihe[0]=1;
        reihe[1]=1;
    }
    reihe[x]=reihe[x-reihe[x-1]]+reihe[x-reihe[x-2]]; //Berechnung der aktuellen Zahl
    printf("%4i", reihe[x]);                 //Trace zum beobachten der Berechnung
    if (x==n-1){
        return reihe[x];         //Rückgabe des gewünschen Ergebnisses
    }
    x++;                        //Weiter zählen
    qRekursiv(n);
}

int main()
{
    int n,q;
    printf("Geben sie ein n ein: ");
    scanf("%i", &n);        //Einlesen der Größe
    q=qRekursiv(n);
    if (q==0){                //Reaktion auf Speichermangel
        printf("Der Speicher reicht nicht aus, um eine so grosse Zahl zu berechnen.");
        return 1;
    }
    printf("\nDie %i-te Q-Zahl lautet: %i", n, q);
    return 0;
}

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

 

[Skyte]

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

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. ^^

#include <stdio.h>
#include <stdlib.h>



int qRekursiv(int n) {
	int *reihe;
	int result;
  reihe=malloc(sizeof(int)*n);
  if (reihe==NULL){
  	return 0;                    //Rückgabe im Fehlerfall
  }
  reihe[0]=1;
  reihe[1]=1;
  
  result = qIntern(n,1,reihe);
  free(reihe);
  return result;
}

int qIntern(int n, int x, int* reihe) {
	if (x == n) {
        return reihe[n-1];         //Rückgabe des gewünschen Ergebnisses
    }
    
    x++;                        //Weiter zählen
    reihe[x] = reihe[x-reihe[x-1]] + reihe[x-reihe[x-2]]; //Berechnung der aktuellen Zahl    
    
    return qIntern(n,x,reihe);
}

int main() {
    int n,q;
    printf("Geben sie ein n ein: ");
    scanf("%i", &n);        //Einlesen der Größe
    q=qRekursiv(n);
    if (q==0){                //Reaktion auf Speichermangel
        printf("Der Speicher reicht nicht aus, um eine so grosse Zahl zu berechnen.");
        return 1;
    }
    printf("\nDie %i-te Q-Zahl lautet: %i", n, q);
    return 0;
}

 

[Chais]

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

greetz Chais

 

[Skyte]

Ok, ist eigentlich logisch, du brauchst das hier:

#include <stdio.h>
#include <stdlib.h>



int qRekursiv(int n) {
	if (n == 1 || n == 2) return 1;
	
	return qRekursiv(n-qRekursiv(n-1)) + qRekursiv(n-qRekursiv(n-2));
}


int main() {
    int n,q;
    printf("Geben sie ein n ein: ");
    scanf("%i", &n);        //Einlesen der Größe
    q=qRekursiv(n);
    if (q==0){                //Reaktion auf Speichermangel
        printf("Der Speicher reicht nicht aus, um eine so grosse Zahl zu berechnen.");
        return 1;
    }
    printf("\nDie %i-te Q-Zahl lautet: %i", n, q);
    return 0;
}