Rekursive Algorithmen - Korrektes Endergebnis

Benutzeravatar
SophiaLi1
Kernelcompilierer
Kernelcompilierer
Beiträge: 542
Registriert: 5. Jan 2014 11:48

Rekursive Algorithmen - Korrektes Endergebnis

Beitrag von SophiaLi1 » 19. Jul 2017 12:08

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?

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Rekursive Algorithmen - Korrektes Endergebnis

Beitrag von Prof. Karsten Weihe » 30. Jul 2017 19:21

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

Benutzeravatar
SophiaLi1
Kernelcompilierer
Kernelcompilierer
Beiträge: 542
Registriert: 5. Jan 2014 11:48

Re: Rekursive Algorithmen - Korrektes Endergebnis

Beitrag von SophiaLi1 » 1. Sep 2017 17:20

Danke!

Antworten

Zurück zu „Archiv“