Seite 1 von 1

Rekursive Algorithmen - Korrektes Endergebnis

Verfasst: 19. Jul 2017 12:08
von SophiaLi1
Hallo,

auf dem 5. Übungsblatt steht für den rekursiven Algorithmus:
Korrektes Endergebnis: Folgt aus Invariante und Abbruchbedingung. Zum Zeitpunkt, da die höchste Rekursionsebene terminiert wurde der komplette Baum betrachtet.
Vorher haben wir allerdings gelernt:
Korrektes Endergebnis: Aus der Invariante folgt, dass der Algorithmus das geforderte Ergebnis zurück liefert. Da der Algorithmus im ersten Rekursionsschritt mit der Wurzel des Baumes aufgerufen wurde, besagt das Ergebnis ob das Element im Baum enthalten ist.
Demnach braucht man für das korrekte Endergebnis bei rekursiven Algorithmen also keine Abbruchbedingung, was für mich auch mehr Sinn macht, da die (zu diesem Zeitpunkt bereits) bewiesene Invariante ja aussagt, dass der Algorithmus für Bäume der Höhe h (= beliebige Höhen) das korrekte Endergebnis liefert.

Also meine Frage: Braucht man die Abbruchbedingung bei rekursiven Algorithmen für das korrekte Endergebnis?

Re: Rekursive Algorithmen - Korrektes Endergebnis

Verfasst: 30. Jul 2017 19:21
von Prof. Karsten Weihe
SophiaLi1 hat geschrieben:
19. Jul 2017 12:08
Also meine Frage: Braucht man die Abbruchbedingung bei rekursiven Algorithmen für das korrekte Endergebnis?
Nein.

KW

Re: Rekursive Algorithmen - Korrektes Endergebnis

Verfasst: 1. Sep 2017 17:20
von SophiaLi1
Danke!