Max. Anzahl von Knoten im Binärbaum

[John Cena]

Hallo,

die Aufgabe in einer Altklausur war, das man eine rekursive Methode in eine iterative umwandeln sollte. Hier der rekursive Code:

public static long anz2 (long h)
    {
        assert (h >= 0);
        if (h == 0)
            return 0;
        else
            return 1 + 2 * anz2(h -1);
    }

Hat auch alles geklappt, hier der iterative Code.

public static long anz (long h)
    {
        assert (h >= 0);
        long anz = 0;
        for (long i = 0; i < h; i++)
            anz = 1+2 * anz;
       
        return anz;
    }

Als letztes steht in der Aufgabe: " Warum lässt sich diese rekursive Funktion besonders einfach iterativ implementieren? " Und da weiß ich nicht genau, was ich da hinschreiben soll. Ich weiß, dass ein Binärbaum der Tiefe T max. 2^T -1 Knoten haben kann, aber ob die das genau damit meinen, weiß ich nicht. Vielen Dank im Voraus.
LG

 

[JStein52]

Was gemeint ist weiss ich auch gerade nicht. Aber ich denke das was du geschrieben hast ist so ziemlich das einzige was nichtr gemeint ist.

 

[John Cena]

Hallo,
Danke für deine Antwort, aber woher bist du dir so sicher, dass man nicht auf diese allgemeine Formel hinauswill?
Mfg

 

[JStein52]

Weil es bei dieser Umformung eigentlich nicht um die Tiefe der Rekursion bzw. um die Länge einer Schleife geht sondern eher um die Art der Rekursion die sich besonders einfach iterativ formulieren lässt . Aber ich habe im Moment auch nicht die richtigen Begriffe parat.