Erklärung: rekursiver Abstieg

[Zephyro]

Hi,

kann mir jemand den "rekursiven Abstieg" erklären. Bei meiner bisherigen Recherche bin ich leider nicht schlauer geworden.
Ich brauch eine normalsterbliche Erklärung.

Der Artikel von Wikipedia hilft mir nicht weiter. Unter einer Rekursion verstehe ich z.B. eine Funktion die sich selbst aufruft etc. In dem Code bei Wikipedia ist aber nur eine If-Verzweigung zu finden.
Warum also "rekursiver Abstieg"? Wie funktioniert das?

Vielen Dank schonmal im Vorraus!

MfG Zephyro

 

[Yuuri]

void recurse( int x )
{
  cout << x << endl;
  if( x > 0 ) recurse( x - 1 );
}

recurse( 5 );

// alternativ über eine Schleife

void recurse( int x )
{
  for( int i = x; i > 0; i-- )
    cout << x << endl;
}

Die Funktion wird so lange aufgerufen, wie x > 0 ist. Mehr ist Rekursion nicht. Analog kann man das auch auf nested Arrays anwenden, also welche, wo eine Tiefe unbekannt ist (bspw. in XML-Dateien) und du alle Elemente durchgehen willst. Da bietet sich Rekursion an im Gegensatz zu Schleifen.

 

[Whiz-zarD]

Unter einer Rekursion verstehe ich z.B. eine Funktion die sich selbst aufruft etc.

Und genau mehr ist es auch nicht.
"Abstieg" deswegen, weil man immer tiefer in den Stack geht.
Die If-Anweisung, die du unter wikipedia findest, ist die sog. Abbruchbedingung.
Irgendwann muss die Rekursion wieder nach oben steigen, ansonsten erhälst du irgendwenn einen Stackoverflow, weil du den Stack mit Funktionen geflutet hast.

Du kannst dir die Rekursion wirklich wie eine Treppe vorstellen, die nach unten führt. Jede Stufe ist ein weiterer Funktionsaufruf. Wenn dann irgendwann mal eine Funktion beendet wird, dann steigst du eine Stufe wieder auf.

 

[Zephyro]

Danke für die schnelle Antworten.

Bei weiteren Unklarheiten, werde ich mich hier erneut melden.


MfG Zephyro

 

[IceMatrix]

Ich habe den Wikipedia-Artikel zwar nicht gelesen. Mit dem Begriff "rekursiver Abstieg" würde ich ein rekursives Durchlaufen einer hierarchischen Datenstruktur (z.B. einem Baum) verbinden. "Abstieg" wegen Wurzel -> Blatt (top-down).