Problem mit rekursion und char als return-wert (C++)

[cuthbert]

wir sollen für unsere c++-vorlesung ein paar kleine programme schreiben. und sind beim thema rekursion angelangt . die aufgabe hab ich im prinzip schnon gelöst, aber ich versteh ein kleines ausgabeproblem nicht. hier mal der code:

#include <cstdlib>
#include <iostream>

using namespace std;
char Baum[16]={'0','+','-','*','c','*','b','-',' ',' ','a','b',' ',' ','d','c'};
char printtree (int i);

main()
{
      int i;
      i=1;
      printtree(i);
      cout<<endl;
    system("PAUSE");
    return EXIT_SUCCESS;
}
[B]char printtree (int i) {
     if (i>7 || Baum[2*i]==' '&& Baum[2*i+1]==' ')
                     return Baum[i];
     
     else {
          cout<<"(";
          cout<<printtree(2*i);
          cout<<Baum[i];
          cout<<printtree(2*i+1);
          cout<<")";
          }[/B]
}

das programm soll einfach den Baum, der zu beginn erstellt wird (Baum[]) in sinnvoller reihenfolge ausgeben. aber das ist nicht mein problem, so weit läuft alles.

irgendwie werden in der fettgedruckten rekursion falsche zeichen ausgegeben und zwar an der stelle

 cout<<")"

hier wird nicht nur die klammer ausgegeben sondern zusätzlich noch ein sonderzeichen. die ausgabe sieht dann so aus:

((c-(a*b)$)$+(b*(d-c)$)$)

die "$"-zeichen sind also zu viel. ich kann mir überhaupt nicht erklären, wie das zustande kommt.

wenn ich die rekursion so umschreibe, dass ich aufs return verzichte und direkt ausgebe:

void printtree (int i) {
     if (i>7 || Baum[2*i]==' '&& Baum[2*i+1]==' ')
                     cout<<Baum[i];
     
     else {
          cout<<"(";
          printtree(2*i);
          cout<<Baum[i];
          printtree(2*i+1);
          cout<<")";
          }

dann klappts einwandfrei. hat jemand ne idee, was ich für einen fehler gemacht hab? ich weiß jedenfalls nicht weiter . letztere Lösung reicht zwar schon für die aufgabe, aber gefällt mir nicht so gut. sorry für die schlechte formatierung, aber der dev c++ editor ist einfach grottig.

 

[7H3 N4C3R]

Hallo,

der else-Zweig in printTree hat kein return. Was dann zurückgegeben wird, ist undefiniert.

Und um pedantisch zu sein der Rückgabewert von main muss int sein. Das Weglassen war nur in C erlaubt.

 

[cuthbert]

hm ok, also meinst du, dass ich auch bei else einfach noch ein zeichen zurückgeben müsste? ich probiers mal aus. danke für den hinweis. mal schauen wie ich das machen kann, ohne dass das ausgegeben wird *grübel*.

Edit:

ah ok, dank deines hinweises hats endlich geklappt

else {
          cout<<"(";
          if (printtree(2*i)!=0)
          cout<<printtree(2*i);
          cout<<Baum[i];
          if (printtree(2*i+1)!=0)
          cout<<printtree(2*i+1);
          cout<<")";
          return 0;
          }

damit läufts jetzt wie gewünscht , hab main () jetzt auch mal ein "int" spendiert. obwohls bei dem anfängerkurs, wohl eh egal ist.

 

[andr_gin]

Also einmal abgesehen davon, dass ich den Sinn des Beispiels nicht ganz verstehen, weil wie kommt man zu dem komischen Feld da oben (soll das ein Baum sein, den man sequentiell abgespeichert hat, aber warum gibst du ihn dann wieder sequentiell aus), würde ich gar nichts zurückgeben, sondern direkt ausgeben, weil sonst musst du im else Zweig auch was zurückgeben und dann noch extra überprüfen, ob das der Fehlercode (z.B. \0) ist. Einfach ein undruckbares Zeichen, das man nicht sieht auszugeben, wäre schlecht, weil auf das kann man sich nicht unbedingt verlassen. Wenn du z.B. \0 verwendest und das Programm wo anders einsetzt, wo du die Zeichen nicht ausgibst, sondern in ein char Array schreibst, dann hast du schon einmal ein Problem, weil der String nach dem ersten \0 aus ist.

Edit: Das ist nicht unbedingt ein typisches Beispiel für eine Rekursion. Es funktioniert zwar, das gebe ich zu und ist vielleicht auch codemäßig kurz, aber wenn man mit Rekursionen anfängt, dann sollte man eher ein typisches Beispiel nehmen wie z.B. ein Directory ausgeben bzw. einen echten Baum, damit man sieht, wo man es einsetzen sollte und wo nicht. Ich habe schon genug Leute gesehen, die dann einfach überall eine Rekursion eingebaut haben, obwohl es eigentlich mit einer Schleife viel besser funktionieren würde und umgekehrt.

Typisches Beispiel für eine Rekursive Baumausgabe (geht auch mit einem normalen Struct:

class node
{
int wert;
node *left;
node *right;

//Konstruktor,Destruktor etc.
};

int main()
{
node *root=new node();

//Baum befüllen

ausgabe(root);
}

void ausgabe(node *current)
{
if(current==NULL)
return;

ausgabe(current->left);
cout << current->wert << endl;
ausgabe(current->right);
}

bzw. ein ähnliches Beispiel in VB.NET:

public sub funktion...
ausgabe("C:\Temp")
end sub

public sub ausgabe(byval dir as string)
for each subdir as string in getdirs(dir) 'Genauer Funktionsname ist nicht so wichtig
ausgabe(subdir)
next

for each file as string in getfiles(dir)
msgbox(file)
next
end sub

Sobald die Rechnerei mit irgendeinem Index anfängt, sollte man sich überlegen, ob das nicht eine normale while-Schleife auch tut.

 

[cuthbert]

ja, das ist ein baum und es war einfach nur ein übungsaufgabe. sinn war einfach nur, den baum wieder auszugeben in einer sinnvollen reihenfolge wie ich ja bereits geschrieben habe und dass man mal ein bisschen mit rekursion rumspielt nichts weiter (es ist halt ne übung und nix produktives).

und dass einfach ausgeben klappt, hab ich ja auch schon gesagt (siehe zweite lösung im ersten post). aber ich wollt halt wissen, wo da speziell mein fehler lag. einfach was anderes machen, hätt mir mit meiner frage nicht weitergeholfen, verstehst du, was ich meine? wie soll ich denn lernen, wenn ich dann einfach ne andere lösung nehm. und ich hab da glaub ich wirklich was sinnvolles gelernt jetzt, auch (oder vor allem) wenns so grundlegend ist, dass man eigentlich von ausgehen müsste, dass das jeder weiß.

 

[cuthbert]

dein beispiel ist ja ganz nett gemeint, aber greift leider erstens schon zu weit voraus, denn von klassen sind wir in unserem anfängerkurs (ein einfacher nebenkurs im ersten semester) noch weit entfernt, und zweitens denkst du anscheinend schon etwas zu praktisch und allgemein, wenn ich das richtig verstanden hab, kannst du mit deiner node klasse quasi mit jedem baum umgehen.

aber die aufgabe lautete halt wirklich nur: geben sie den baum blabla (siehe den baum, den ich definiert hab) mit diesen und jenen bestimmten bedingungen aus in dem sie in der main funktion eine rekursive funktion printtree aufrufen, welche mit dem index 1 gestartet wird.

und perfekt das macht mein programm. nicht mehr und nicht weniger.

aber trotzdem danke für den ratschlag. nächstes semester werd ichs dann wahrscheinlich auch vollständig verstehen .

 

[andr_gin]

1.) Naja dein Programm geht im Moment, aber auch nur deshalb, weil du die Zeichen gleich auf den Bildschirm schreibst und dadurch die ganzen \0, die drin sind nicht siehst. In Wirklichkeit schaut den String so aus: ((c-(a*b)\0)\0+(b*(d-c)\0)\0) Aussehen sollte er aber so: ((c-(a*b))+(b*(d-c)))
Wenn du die Daten auch nur einmal irgendwo zwischenspeicherst, dann schneidet er bei der ersten \0 ab und du hast nur mehr: ((c-(a*b)
Nur weil ein Programm gerade zufällig mit der Eingabe das richtige ausgibt, heißt das noch lange nicht, dass es funktioniert.

2.) Wenn ihr noch kein Strukturen gemacht habt (Klassen sind eigentlich nicht notwendig) bzw. keine Pointer, dann macht es nicht wirklich Sinn, dass ihr schon mit Rekursionen anfangt. Da ist einfach die Reihenfolge verdreht. Das, was ihr da habt, heißt nur zufällig Baum und ihr gebt es mit Gewalt so aus wie einen, aber es ist kein Baum. Leider machen das viele Lehrer so. Das ist in etwa so, wie wenn man in der Fahrschule ein altes Lenkrad in die Hand nimmt und sich dann auf einen Sessel, den man Auto genannt hat, hinsetzt und laut brumm brumm schreit und hin und her lenkt, weil man erst 14 ist und noch keinen Führerschein machen darf, aber trotzdem schon das lenken lernen will.

 

[cuthbert]

hm, ja dass mit dem speichern hab ich mir auch überlegt. aber ich denke mal dafür bräuchte man ne art stack, aber das kenn ich eben auch noch nicht.

und wie gesagt wir hatten bis jetzt wie gesagt weder klassen noch strukturen, aber wird sicher dann im nächsten semester kommen....

zumindest versteh ich ja, was mein programm ausgibt und das reicht erst mal, zumindest dafür.

 

[7H3 N4C3R]

Das, was ihr da habt, heißt nur zufällig Baum und ihr gebt es mit Gewalt so aus wie einen, aber es ist kein Baum.

Öh... und warum sollte das kein Baum sein? Es geht um die Datenstruktur Baum, nicht um eine ganz bestimmte programmtechnische Realisierung. Ich finde es persönlich schade, wenn einem da ausschließlich verzeigerte Strukturen/Klassen in den Sinn kommen (mal ganz von der Behauptung abgesehen, Rekursion macht ohne Pointer/Strukturen keinen Sinn).

Einen (vollständigen Binär-) Baum auf ein Array abzubilden ist ganz nebenbei eine häufige und gute Lösung (geringer Speicherbedarf, performanter Zugriff (man kann sich den Index einfach errechnen), einfache persistente Speicherung).

 

[cuthbert]

versteh ich allerdings auch net so ganz. die erste (bzw nullte stelle) wurde ausgelassen, damit die rechung aufgeht.

die nachfolger eines knotens i stehen somit immer an der stelle 2*i (links) und 2*i+1 (rechts). für micht ist das ne sinnvolle art, einen baum zu speichern. naja, was anderes kenn ich ja noch nicht. ursprünglich hatten wir nur den baum bekommen und das array sollten wir dann nach dem algorithmus selbst erstellen. dass die klammern (also die komplette ausgabe) nicht schon im baum stehen, hat ja nix damit zu tun, oder was meinst du?

heißt btw net mehr lehrer sondern professor inzwischen , aber hätt wohl genauso gut auch noch in der schule dran kommen können.