Rekursionen verstehen in C

Schnelle objektorientierte, kompilierende Programmiersprache.
Antworten
Xeon
Beiträge: 169
Registriert: So Dez 17, 2017 4:10 pm

Rekursionen verstehen in C

Beitrag von Xeon » Mo Apr 08, 2019 2:00 pm

Hallo zusammen,

ich lerne Programmieren mit dem Buch: C von A bis Z von Jürgen Wolf. Beim Kapitel 22 geht es um Binäre Bäume, dort werden Rekursionen behandelt. Leider verstehe ich das Thema Rekursionen nicht ganz. Kennt jemand eine Quelle wo es ausführlich erklärt wird?

Hier ist der Code den ich nicht verstehe:

Code: Alles auswählen

//Funktion zum ermittelt der Höhe des Baumes
int hoehe(KNOTEN *zeiger) //Wurzel wurde an diese Funktion übergeben
{
    int hlinks, hrechts;

    if(zeiger == NULL)
    {
        return 0;
    }
    else //Was geschieht hier?
    {

        hlinks = hoehe(zeiger->links);
        hrechts = hoehe(zeiger->rechts);
        if(hlinks > hrechts)
        {
            return hlinks+1;
        }
        else
        {
            return hrechts+1;
        }
    }
}
Nehmen wir an dies ist mein Baum:
Du hast keine ausreichende Berechtigung, um die Dateianhänge dieses Beitrags anzusehen.

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Rekursionen verstehen in C

Beitrag von Xin » Mo Apr 08, 2019 2:27 pm

Xeon hat geschrieben:
Mo Apr 08, 2019 2:00 pm
Hallo zusammen,

ich lerne Programmieren mit dem Buch: C von A bis Z von Jürgen Wolf. Beim Kapitel 22 geht es um Binäre Bäume, dort werden Rekursionen behandelt. Leider verstehe ich das Thema Rekursionen nicht ganz. Kennt jemand eine Quelle wo es ausführlich erklärt wird?
Die etwas gemeine Erklärung ist hier:
https://www.proggen.org/doku.php?id=glossary:recursion

Etwas ausführlicher findet man das ganze hier:

https://www.proggen.org/doku.php?id=c:t ... :recursion
https://www.proggen.org/doku.php?id=algo:recursion

Hier ist der Code den ich nicht verstehe:

Code: Alles auswählen

    else //Was geschieht hier?
    {
        hlinks = hoehe(zeiger->links);
        hrechts = hoehe(zeiger->rechts);
        if(hlinks > hrechts)
        {
            return hlinks+1;
        }
        else
        {
            return hrechts+1;
        }
    }
}
Du stehst irgendwo am Baum und fragst ob links oder rechts ein Knoten ist. Wenn nicht: 0. Falls doch, fragt dieser Knoten wieder, ob da links und rechts etwas ist. Das unterste Blatt gibt 0 zurück. Jeder darüber liegende Knoten, der gefragt, addiert 1 auf diesen Wert. Also 30, 42 und 50 geben 1 zurück: da ist nichts (0) mehr drunter und da wird 1 aufaddiert. 45 bekommt also links und rechts 1 zurück, keins ist größer, also nimmt es die 1 und addiert 1 drauf. 45 gibt also 2 zurück. 40 erhält von 30 1 zurück und von 45 die 2. 2 ist größer als 1, also nimmt 40 die 2 von der 40 und addiert 1 drauf. Die 3 gibt es dann an die 10 zurück. Die 10 erhält rechts nun die 3 und links die 0. 3 ist größer als 0, also addiert es 1 auf die 3 und gibt 4 zurück.
Der Baum hat eine Höhe von vier Ebenen: 10, 40, 45, 50 oder 10, 40, 45, 42. Nach maximal vier Schritten ist man an einem Blatt.

Du läufst so jeden möglichen Weg im Baum nach unten und fängst immer bei einem Blatt an zu zählen, wie lange Du wieder hochlaufen musst. Den längeren Weg gibst Du weiter.

Du fragst erst den obersten Knoten und der fragt genauso seine Unterknoten. Das wiederholt sich solange, bis die Abbruchbedinungen erreicht, der sogenannte Rekursionsanker:

Code: Alles auswählen

  if(zeiger == NULL)
    {
        return 0;
    }
 
Hier wird jetzt kein Kind mehr gefragt und die Sache abgebrochen.
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Antworten