Rekursion in C

[Rene Albrecht]

Hi@all,

ich habe dringendes Interesse an rekursiven Funktionen in C und brauche Eure Hilfe.

Ich habe folgende Aufgabe zu lösen: eine Bahn soll über mehrere Zwischenstationen inkl. weiterer abgehender Verbindungen den Weg zu einem definierten Zielbahnhof selbstständig finden.

Da das ganze in C zu realisieren ist und ich weder in den Tutorials noch in der Rubrik allgemeine Programmierung hier fündig werden konnte bitte ich Euch hier um Hilfe!

Danke
René

 

[RedWing]

Also wenn du wissen willst was eine Rekursive Funktion ist:

Eine rekursive Funktion ist eine Funktion die sich ständig selber aufruft.

Bsp.:

func fak(t: nat):nat begin
   
   if(t == 0)
        return 1;
   else
        return t * fak( t - 1);
end

Das wäre ein Beispiel für lineare Rekursivität, das heist das ein aufruf von fak in höchstens jeder Fallunterscheidung einaml auftritt.
Im Speicherbild würde sich der Stack dann auch linear vergrößern da immer wieder
neuer Speicherplatz für den Parameter t benötigt wird und der Speicher ja noch von dem vorigen Funktionsaufruf vorhanden ist...
Wenn die Rekursion dann sozusagen ganz "unten" angekommen ist (t == 0) wird der Speicher wieder abgebaut.

Als zweiten Typus gibt es die kaskadenartige(baumartige) Rekursion. Welche exponential ansteigt. In jedem Zweig kommen zwei oder mehr Funktionsaufrufe von binom vor...(auch exponentielles Anwachsen des Speichers...

Bsp.:

func binom(n: nat, m: nat):nat
begin

   if( m == 0 || n == m) return 1;
   else
       return (binom(n-1,m) + binom(n-1,m-1));
end

(Dieses Bsp entspricht denm Binominialkoeffizienten n über k in der Mathematik)

Insgesamt gesehen ist rekursive Programmierung eine sehr elegante Programmierung aber nicht immer effizient genug...

Das wäre zum Thema rekursion, was ich mir noch aus meinem Studium aus den Fingern saugen konnte
Ich hoffe ich konnts einigermaßen verständlich rüberbringen.

Viele Grüsse

RedWing

 

[Kachelator]

@Redwing:
Danke, dass du dir so viel Mühe mit der Erklärung der Rekursion gegeben hast. Ich bin mal so frei und nehme deine erste Funktion und mache C daraus, weil Rene damit wahrscheinlich mehr anfangen kann.

int fakultaet( int t )
{
  if ( t == 0 )
    return 1;
  else
    return t * fakultaet( t - 1 );
}

@Rene:
Deine im ersten Post geschilderte Aufgabe ist bereits relativ anspruchsvoll. Vermutlich habt ihr dazu vorbereitende Aufgaben zur Rekursion gehabt. Ist dein Problem das Verständnis der Rekursion an sich, oder kannst du das und hast nur Schwierigkeiten, die oben geschilderte Aufgabe in den Griff zu bekommen? Könntest du uns deine Lösungsansätze zeigen? Das würde es uns einfacher machen, dir zu helfen.

 

[Rene Albrecht]

@RedWing:
Danke für Deine Erläuterungen. Ich habe mir mal im Buch "C-Programmierung" von Addison-Wesley den Bereich über Rekursion durchgelesen und bereits einigermaßen verstanden (dort sind auch die Nachteile der Rekursion klar dargestellt).

@Kachelator:
Das Problem ist wirklich nicht so trivial. Ich habe im Rahmen einer C-Einführung (praktischer Programmierkurs) mal mittels Rekursion mal berechnet, wie ein Pferd auf einem Schachfeld springen muß um alle Felder genau einmal zu erreichen. Seitdem habe ich damit leider überhaupt keine Erfahrungen mehr sammeln können. Daher kann ich noch nicht einmal einen Lösungsansatz für mein Problem bieten - baue also erstmal vollkommen auf Eure Erfahrungen...

Könnte man mein Problem evtl. auch ohne Rekursion berechnen? Und wenn ja: wie würdet Ihr da rangehen?

Dank und Gruß
René

 

[RedWing]

Eine Frage zum Verständniss:

Du hast angenommen 12 Bahnhöfe und der Zug soll für einen dieser 12 Bahnhöfe einen Zielbahnhof auswählen und diesen Bahnhof unter Mitnahme der anderen Elf erreichen?
Und du sollst jetzt prüfen ob das möglich ist, oder wie kann man das verstehen?
Soll der Zug den weg selber finden, oder soll ein Benutzer den Zug steuern?
Oder kannst du mal die Aufgabe nochmal ein bisschen genauer erläutern?

Gruß

RedWing

 

[Kachelator]

Das Bahnhöfe-Problem ist dem Schach-Problem ziemlich ähnlich. Der grosse Unterschied ist die Datenstruktur, die durchwandert werden muss, um eine Lösung zu finden. Das Schachbrett lässt sich leicht mit einem zweidimensionalen Array repräsentieren. Für die Bahnhöfe würde sich ein Netz von Knoten und Verbindungen anbieten.

Vielleicht legst du zwei Arrays an:
Nehmen wir an, du hast n Bahnhöfe.
Im ersten speicherst du für jeden der Bahnhöfe, ob er schon besucht wurde.
Das zweite Array ist zweidimensional. Du trägst dort für jedes Bahnhofspaar ein, ob eine Verbindung besteht.
Wenn du die Daten soweit astehen hast, kannst du deinen Schachalgorithmus vermutlich leicht geändert einsetzen, um eine Verbindung zwischen einem Startbahnhof und einem beliebigen Zielbahnhof sucht.

Das Ganze liesse sich selbstverständlich auch ohne Rekursion lösen, aber oft ist Rekursion der elegantere Weg.

 

[Rene Albrecht]

Original geschrieben von RedWing
Du hast angenommen 12 Bahnhöfe und der Zug soll für einen dieser 12 Bahnhöfe einen Zielbahnhof auswählen und diesen Bahnhof unter Mitnahme der anderen Elf erreichen?
Und du sollst jetzt prüfen ob das möglich ist, oder wie kann man das verstehen?
Soll der Zug den weg selber finden, oder soll ein Benutzer den Zug steuern?
Oder kannst du mal die Aufgabe nochmal ein bisschen genauer erläutern?

Ich glaube, Kachelator hat das Problem schon recht gut verstanden: ich habe z.B. zwölf Bahnhöfe (quer verstreut über ein Gebiet). Nicht alle Bahnhöfe sind direkt miteinander verbunden, aber jeder ist von jedem aus erreichbar (über Zwischenstationen). Aufgabe wird jetzt z.B., von Bahnhof 3 zu Bahnhof 9 zu fahren - bzw. alle dafür nötigen Wegpunkte herauszufinden.

@Kachelor: der Ansatz hört sich vielversprechend (und verständlich) an. Allerdings habe ich keine Ahnung mehr, wie die Rekursion dazu aussah (die Schachbrett-Übung hab ich vor 8 Jahren gemacht und ich habe natürlich keine Sourcen mehr ).

 

[RedWing]

Die Lösungsvorschlag von Kachelor is schon nicht schlecht,
jetzt musst du dir halt überlegen wie dus am besten agehst?

Frage 1: Musst dus unbedingt rekursiv machen, sehe den Vorteil in der Aufgabe nicht so ganz.

Also du durchsuchst das Feld um den entsprechenden Anfangsbahnhof zu finden.
Dazu findest du natürlich einen Zielbahnhof(Bahnhöfe im anderen Feld abhacken, weil sie schn erreicht wurden)=> dein neuer Startbahnhof
Feld wieder durchsuchen=>Zielbahnhof gefunden=> dein neuer Startbahnhof
Solange machen bis alle Bahnhöfe erreicht wurden, oder wenn ein Bahnhof schonmal erreicht wurde(weil dann bist du im Kreis gefahren) oder der neu gefundene Bahnhof gleich deinem Zielbahnhof ist.

Und das ganze sieht mir ziemlich nach nen iterativen Algo aus also wieso rekursiv...

Gruß

RedWing

 

[Rene Albrecht]

@RedWing:

Irgendwie versteh ich jetzt nur noch Bahnhof! Der Ansatz hört sich (wie bei Kachelator) gut an - wenn Du das jetzt noch in einen Algorithmus bringen könntest...

Nachtrag: Natürlich muß es nicht rekursiv sein. Ich hielt es für die kürzeste Möglichkeit, mein Problem in den Griff zu bekommen (und ich dachte dieses Problem auf eine ähnlich simple Art lösen zu können wie das Schachproblem, wenn mir nur erstmal wieder ein Lich aufgehen würde).

 

[Kachelator]

Das trifft auch zu. Hast du schon die Daten so organisiert, dass du das Streckennetz in der von mir vorgeschlagenen Weise speichern kannst?

Dann wählst du einen Startbahnhof und einen Zielbahnhof.

Die rekursive Funktion -- nennen wir sie mal "reise()" -- sieht etwa so aus:

const int anzahl_der_bahnhoefe = 12;
bool schon_besucht[ anzahl_der_bahnhoefe ];

// dies repraesentiert das Streckennetz
bool strecke_existiert_von_nach[ anzahl_der_bahnhoefe ][ anzahl_der_bahnhoefe ];
// muss etwas so gefüllt werden:
//   a b c d 
// a 0 1 1 0
// b 1 0 0 1
// c 1 0 0 0
// d 0 1 0 0
// hier gibt es Verbindungen zwischen ab,ac,ba,bd,ca,db
// ab heisst von "a nach b", da es keine 
// Einbahnstrassen sind, ist auch ba nötig

int Startbahnhof = 0;
int Zielbahnhof = 11;

int geschafft = false;

void reise( int aktuellerBahnhof, int level )
{
  if ( schon_besucht[ aktuelleBahnhof ] ) return;
  
  if ( aktuellerBahnhof == Zielbahnhof )
  {
    cout << "Hurra, wir sind da nach "  << level << " Streckenabschnitten!";
    geschafft = true;
    return;
  }
 
  // als besucht markieren
  schon_besucht[ aktuelleBahnhof ] = true;
  
  // alle nachbarknoten besuchen
  for ( int i = 0; i <= anzahl_der_bahnhoefe; ++i )
  {
    if ( i == aktuellerBahnhof ) continue;
    
    if ( strecke_existiert_von_nach[ aktuellerBahnhof ][ i ] )
    {
      reise( i, level + 1 );
    }
  }
}


int main()
{
  // hier daten initialiseren 
  //(Streckennetz)
  //(schon_besucht[] alle auf false setzen)
  
  reise( Startbahnhof, 0 );
  
  if ( !geschafft )
  {
    cout << "Es gibt keine Verbindung";
  }

  return 0;
}

Hm, das sollte dich ein Stück weiterbringen. Ich habe es nicht kompiliert; wahrscheinlich sind noch Fehler drin (und Lücken sowieso!), damit es nicht zu einfach wird.