C: Rekursion Problem

[Fragant (Gast)]

hallo,

ich will mithilfe der Rekursion ein Programm schreiben, bei dem für eine 
bestimmte länge alle binärzahlen angegeben werden.
Bsp(länge=2): 00,01,11


Das Problem liegt an der Ausgabe, da diese nun "für jede Ebene" getätigt 
wird. Wie bekomme ich es hin, dass die Ausgabe nur einmal stattfindet?
PS: eine abbruchbedingung für die weiteren "Ebenen" fällt mir keine ein
--------------------------------------------------------------------
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
#include <time.h>


void dezinbin(char zahlen[], int anzahl, int laenge, int i, int zahl)
{

  int rest;




    if (i >= 0){
      rest = zahl % 2;
      zahl = zahl / 2;
      zahlen[i] = rest + 48;
      i--;
      dezinbin(zahlen, anzahl,laenge, i, zahl);
    }


      printf("Zahl[%d]= ", zahl);
      for (int z = 0; z < laenge; z++){
        printf("%c", zahlen[z]);
      }
      printf("\n");
}


int main()
{
  int laenge;
  int anzahl=2;
  int ergebnis = 0;
  int i, zahl;
  char zahlen[100];



  printf("Geben Sie die Laenge der Binaerzahlen an:\n");
  scanf("%d", &laenge);

  for (int i = 1; i < laenge; i++){
    anzahl = 2 * anzahl;
  }

  printf("Es gibt %d verschiedene Binaerzahlen (0 bis %d)\n", anzahl, 
anzahl-1);
  printf("Die Binärzahlen lauten:\n");

  i = laenge - 1;
  for (int k = 0; k < anzahl; k++){
    zahl = k;
    dezinbin(zahlen,anzahl, laenge, i, zahl);
  }
  //for (int z = 0; z < anzahl; z++){
  //  printf("(%d):", z);
  // }

  system("pause");
  return 0;
}

------------------------------------------------------------------

[Peter II (Gast)]

wozu überhaupt die Rekursion?

Wenn du schon von 1 bis N zählst hast du doch schon alle Möglichkeiten. 
Du brauchst da doch nur noch die Ausgabe?

for (int k = 0; k < anzahl; k++){
    Ausgabe(k);
}

jetzt brauchst du nur noch Ausgabe zu programieren.

[Fragant (Gast)]

Die Lösung mit der Rekursion ist Teil der Aufgabe!

Habe die Ausgabe doch schon in der Funktion dezinbin() reingemacht:

 printf("Zahl[%d]= ", zahl);
      for (int z = 0; z < laenge; z++){
        printf("%c", zahlen[z]);
      }
      printf("\n");

[Fragant (Gast)]

habs nun hinbekommen !

[Peter II (Gast)]

Fragant schrieb:
> Habe die Ausgabe doch schon in der Funktion dezinbin() reingemacht:

ja, aber das ist ja das Problem.

So wie du es gemacht hast, macht es wenig sinn.

Wenn du schon mit Rekursion arbeiten sollst, dann muss jeder Aufruf nur 
eine Stelle berechnen. Für die nächste stelle kommt dann die Rekursion. 
Und wenn du bei der stelle bis, die in länge angeben ist erfolgt die 
ausgabe.

Deine Rekursion hat viel zu viele unötige Parameter.

nur mal schnell getippt ohne tests

void foo(data[], int pos, int maxPos ) 
{
   if ( pos == maxPos ) {
      printf("%s\n", data );
      return;
   }

   for( int i = 0; i < 2; ++i ) {
      data[pos] = i+'0';
      foo( data, pos+1, maxPos );
   }

}

int length = 5;
char[5] data;

foo(data, 0, length);

[Hinz (Gast)]

Zahl die Aufrufe in einer lokalen static Variable.

[Yalu X. (yalu) (Moderator)]

Dein Programm erzeugt die in Frage kommenden Zahlen als Integer-Werte
nichtrekursiv in einer Schleife. Die Extraktion der einzelnen
Binärziffern erfolgt dann mit einem rekursiven Algorithmus.

Ich bin mir fast sicher, dass der Aufgabensteller eine andere Lösung im
Kopf hatte, nämlich die direkte Erzeugung der Binärzahlen als Array oder
Liste der einzelnen Ziffern und das Ganze natürlich rekursiv und ganz
ohne Schleife. Die Frage ist nur, ob er die Aufgabe auch präzise genug
gestellt hat, um andere Lösungen auszuschließen. Schau dir also am
besten noch einmal die genaue Formulierung der Aufgabe an.

[root (Gast)]

f 0 = ""
f n = if n `mod` 2 == 1 then (f n')++"1" else (f n')++"0" where n' = n `div` 2

res = takeWhile (\x->length(x)<=5) $ map f [1..]

[Yalu X. (yalu) (Moderator)]

root schrieb:
> f 0 = ""
> f n = if n `mod` 2 == 1 then (f n')++"1" else (f n')++"0" where n' = n
> `div` 2
>
> res = takeWhile (\x->length(x)<=5) $ map f [1..]

Auch du gehst hier den Weg über Integer-Zahlen, aus denen dann die
einzelnen Bits extrahiert werden. Der direkte Weg ginge so:

b 0 = [""]
b n = map ('0':) b' ++ map ('1':) b' where b' = b (n-1)

b n liefert eine Liste aller Binärzahlen mit n Ziffern, so z.B.

b 3  ->  ["000","001","010","011","100","101","110","111"]

Da explizite Rekursionen mittlerweile auch in der funktionalen
Programmierung etwas aus der Mode gekommen sind, ist hier noch eine
elegantere Variante, die ohne sie auskommt:

b n = replicateM n "01"

oder, wenn man es lieber pointfree mag:

b = flip replicateM "01"

Die Rekursion ist nach wie vor vorhanden, versteckt sich aber irgendwo
ganz tief in der Funktion replicateM.

Das alles ist aber offtopic, denn eigentlich sollte die Aufgabe ja in C
gelöst werden.

[D. I. (Gast)]

Ohne weiteren Input zur Aufgabenstellung und wenns nur um die Ausgabe 
geht:

#include <stdio.h>


void printRecursive(char *bin, int currentDepth, int maxDepth)
{
  if (currentDepth == maxDepth)
  {
    printf(bin);
    printf("\n");
    return;
  }
  bin[currentDepth] = '0';
  printRecursive(bin, currentDepth + 1, maxDepth);
  bin[currentDepth] = '1';
  printRecursive(bin, currentDepth + 1, maxDepth);
}

int main(int argc, char *argv[])
{
  const int MAX_DEPTH = 20;
  char bin[MAX_DEPTH] = { 0 };

  int depth = 2;

  printRecursive(bin, 0, depth);
  return 0;
}

[Peter II (Gast)]

D. I. schrieb:
> Ohne weiteren Input zur Aufgabenstellung und wenns nur um die Ausgabe
> geht:

toll, fast die gleiche Lösung gab es schon vor mehr als 16 stunden.

[Yalu X. (yalu) (Moderator)]

Peter II schrieb:
> toll, fast die gleiche Lösung gab es schon vor mehr als 16 stunden.

Irgendwie habe ich deinen Beitrag vom 11.05.2015 21:39 ebenfalls
übersehen. Das ist aber ziemlich genau die Lösung, von der ich denke,
dass sie dem Aufgabensteller vorschwebte.

Nur damit keine Missverständnisse entstehen: Mein Kommentar vom
11.05.2015 23:14 bezog sich natürlich nicht auf deinen Vorschlag,
sondern auf die Lösung des TE.