Rekursion

Hallo Jungs.
Ich hab eine sehr wichtige Frage an euch:
DIE AUFGABE:
"Entwickeln Sie eine rekursive Funktion, die alle Binärzahlen einer vom Anwender einzugebenden Länge ausgibt. Die Binärzahlen sollen aber nicht durch irgendwelche Algorithmen erzeugt werden, sondern durch eine for-Schleife für jede Stelle der Binärzahl. Der Zähler dieser for-Schleife soll von 0 bis 1 laufen."

Was ich bis jetzt habe ist das:

#include <stdio.h>

int bin (int a){
int i;
if (a>0){
for (i = 0 ; i<2; i++){
printf ("%d", i);
bin (a-1);
}
}
else
printf ("\n");
return 0;
}

int main()
{
int c;
c = 3;
bin (c);
getchar ();
return 0;
}

Die Ausgabe auf dem Bildschirm ist allerdings:
000
1
10
1
100
1
10
1
Es sollte aber so aussehen:
000
001
010
011
100
101
110
111

Wenn irgendjemand einen Vorschlag hat, wie ich dieses Problem lösen kann, wäre ich wirklich sehr, sehr, sehr, sehr (...) dankbar, wenn er diesen hier kundtut.

MFG

hat keiner ne ahnung?
nicht mal ein kleinen tipp?

Entyl_Sa

wenn du die letzte 1 ausgibst dann fehlen dir die Zeichen die bein ersten Schleifendurchlauf vor der 0 standen, die solltest du irgendwo mitführen und dann eine Ausgabe nur in der letzten Rekursionstiefe machen, so zumindistens wuerde ich das machen.

Könntest Du das mal mit'n bissl code verdeutlichen. Also so wie ich das sehe, kann man nicht einfach in der letzten rekursionsebene alles ausgeben lassen, denn sobald man ein "printf" ind die funktion schreibt, wird ja in jeder rekursionsebene etwas ausgegeben. Oder?

Entyl_Sa

Also so in etwa hatte ich mir das vorgestellt, obwohl mir die Lösung gerade selber nicht so gut gefällt, weil für jeden Funktionsaufruf das char array angelegt wird, das sollte man vielleicht dynamisch nur in der Grösse anlegen in der man es braucht.

#include <stdio.h> 

void bin(int a, char * s){
	char c[256];
	if(a>0){
		for(int i=0;i<2;i++){
			sprintf(c,"%s%d",s,i);
			bin(a-1, c);
		}
	}
	else{
		printf("%s\n",s);
	}
}

int main()
{
	int c;
	char * s = "";
	c = 3;
	bin (c,s);
	getchar ();
	return 0;
}

Gruß Entyl Sa

JUHU
Es funktioniert!!
VIELEN, VIELEN, VIELEN Dank.
Würd' das auch mit 'nem Feld funktionieren?

Ich hab das so weit glaub' ich jetzt verstanden. Aber wieso gibst du am Ende s aus, und nicht c?
Durch "sprintf" werden doch alle Zahlen in c gespeichert, oder?

Könntest du vielleicht (bitte, bitte) die Vorgehensweise des Programms etwas erläutern ?

Entyl_Sa

#include <stdio.h> 

void bin(int a, char * s){
	char c[256];	//Platz um den neuen string zu speichern
	if(a>0){		//wenn noch mehr Binärstellen benötigt
		for(int i=0;i<2;i++){
			sprintf(c,"%s%d",s,i);	//String mit zusätzlicher Stelle in c ablegen
			bin(a-1, c);			//rekursiver aufruf
		}
	}
	else{					//wenn die Funktion aufgerufen wird (mit a == 0)
							//also keine weitere Stelle benötigt
		printf("%s\n",s);	//hier in s liegt jetzt der komplette string
							//c ist an dieser Stelle garnicht belegt
	}
}

int main()
{
    int c; 
    char * s = "";
    c = 3; 
    bin (c,s); 
    getchar (); 
	return 0;
}

Die Zahlen werden in c gespeichert und c wird dann an den nächsten rekursiven Aufruf übergeben, ist also dann s. Also brauche ich am Schluss(a==0) nur s ausgeben, denn da habe ich ja schon ausreichend Stellen.

Gruß

Entyl Sa

Ok. Ich hab es kapiert. Nur noch zwei klitzekleine Fragen:

1. Wieso muss s ein Zeiger sein?

2. Nachdem s zum ersten mal als "000" ausgegeben worden ist, wird die for - Schleife wieder aufgerufen. Warum ist die nächste Ausgabe dann nicht "000001", der Wert in s wird ja nicht vorher gelöscht?

Das sind bestimmt sehr nervige Newbie Fragen, umso dankbarer bin ich, das Du die mir alle beantwortest!!

Entyl_Sa

Also, wieso muss s ein Zeiger sein? Gute Frage!
Ich kann anstelle von

void bin(int a, char * s)

schreiben

void bin(int a, char s[])

das ist vom Typ her gleich.
In main kann ich allerdings kein Array der grösse 0 anlegen, also muss ich hier einen char * anlegen.

Bem.: beim Array wird der Speicher (hier nicht dynamisch auf dem Stack) angelegt und ich kann den Zeiger nicht umsetzen. Ein char * ist ein Zeiger auf chars die irgendwie angelegt sind, hier kann ich den Zeiger auch auf eine andere Addresse zeigen lassen.

Das s was ich ausgeben lasse existiert ja nach der Ausgabe nicht mehr da die Funktion danach ja endet. In der Stufe darüber wird das c dann überschrieben und die Funktion dann wieder mit c aufgerufen, welches dann in der tieferen Stufe wieder zum s wird und ausgegeben wird.

Gruß Entyl Sa

OK, neue Fragen :

1. Wieso kann man in main kein Feld (array) mit Größe 0 anlegen?

2. Es ist ja schön und gut, dass der Zeiger auf verschiedene Adressen zeigen kann, dass wird in dem Programm aber nicht benötigt/genutzt, oder?

Nochmal ein RIESENGROSSES Dankeschön an Dich.
Entyl_Sa rulez

Entyl_Sa

Ein Array mit 0 (sprich ohne) Elemente, wie stellst du dir das den vor? Sowas gibt es einfach nicht.

Du hast recht, ich setze den Zeiger nirgendwo um, und eigentlich beschwere ich mich immer bei Leuten die Arrays in der Pointernotation übergeben, also schreib mal lieber char s[] dann ist es besser lesbar (aber immer noch das selbe).

dass der Zeiger auf verschiedene Adressen zeigen kann,

Diese Formulierung laesst den Schluss zu das ein Zeiger gleichzeitig auf zwei verschiedene Adressen zeigen kann, das ist natuerlich nicht der Fall.

Nun gut, ein kleiner Test:

Der Funktion werden zwei Werte übergeben: eine integer, die ein Wert gleich der Größe der Stellenzahl der Binärzahlen, die ausgegeben werden sollen, hat und ein Character ohne Elemente.
In der Funktion wird ein zweiter Character mit 256 Zeichen initialisiert.
Wenn a größer 0 ist wird eine for - Schleife ausgeführt mit der Variablen i, die von 0 aufwärts gezählt wird.
Innerhalb dieser Schleife wird mit dem Kommando "sprintf" der Wert des Strings s und der Variablen i in c abgespeichert.
Danach wird die Funktion rekursiv aufgerufen und die Werte a-1 und c werden übergeben, wobei der Wert von c in s gespeichert wird.
Wenn a den Wert 0 annimmt, ist die Abbruchbedingung der rekursiven Funktion erfüllt und der String s wird auf dem Bildschirm ausgegeben.

Sehr schlechtes Deutsch, tausende von grammatikalischen Fehlern, aber logisch doch richtig, hoffe ich. Oder nicht????

Entyl_Sa

Fast richtig.

Danach wird die Funktion rekursiv aufgerufen und die Werte a-1 und c werden übergeben, wobei der Wert von c in s gespeichert wird.

Das stimmt so nicht ganz. Der Wert von c wird nicht in s gespeichert, sondern die Funktion wird mit c aufgerufen, und dann wird dieses c in der neuen Instanz mit s angesprochen.

Ein kleines Beispiel

bin1:
ruft bin2 auf mit a-1 und c
bin2(a-1, c)

bin2:
hier ist s das gleiche wie c in bin1

Aber vielleicht war dir das ja schon klar und du hast dich nur falsch ausgedrückt.

Gruß Entyl Sa

DrZoidberg

Entyl_Sa schrieb:

Also so in etwa hatte ich mir das vorgestellt, obwohl mir die Lösung gerade selber nicht so gut gefällt, weil für jeden Funktionsaufruf das char array angelegt wird, das sollte man vielleicht dynamisch nur in der Grösse anlegen in der man es braucht.

Kein Problem:

#include <stdio.h>  

void _bin(int laenge, int pos, char c[]) {
    int i;
    if(pos<laenge){
        for(i=0;i<2;i++){
            c[pos]=i+'0';
            _bin(laenge, pos+1, c);
        } 
    } 
    else{                   
        printf("%s\n",c);    
    } 
}

void bin(int laenge) {
    char c[laenge+1];
    c[laenge]='\0';
    _bin(laenge, 0, c);
}

int main() 
{ 
    int c;
    c = 3;  
    bin (c);  
    getchar ();  
    return 0; 
}

DrZoidberg

CasperMcKool schrieb:

"Die Binärzahlen sollen aber nicht durch irgendwelche Algorithmen erzeugt werden, sondern durch eine for-Schleife für jede Stelle der Binärzahl."

Solch ein Satz kann auch nur von einem Lehrer stammen.

Is aber von einem Professor