[Playlisten] [Impressum und Datenschutzerklärung]

12.02.2 Iteration und Rekursion


CC-BY-NC-SA 3.0

Tempo:

Anklickbares Transkript:

zweigroße Begriffezwei weitere große Begriffezu den Algorithmen Interaktionund Rekursionsiterationund Rekursiondas sind zwei Grundprinzipien?? man Algorithmen bauen kanndie Iterationist das was sie als Schleife schon kennen eines while-Schleifeeine for-Schleifedas Föderationgehe die Fälle zu Fuß durch vom ersten bis zum letzten Besitz endlich fertig isteine Wiederholungsrekursionist das ich eine Funktion selbst aufruftin C würde man das so schreiben meine Funktion ruft sich selbst aufdas wäre Rekursionistauf einenVerfahrens ?? sehr elegant hinzu schreibenes kostetgerne malSpeicherplatzdurch diese vielen Aufruf ungewöhnlich vorsichtig ist dauert auch extrem lang aber es kann ein sehr elegantes Verfahren sein Rekursion anzuwendendas haben wir gerade gesehen bei demBubblesorterstmals nochmals ineiner schematischich habe eine Listeund wende auf diese Liste eine Funktion ein malig die mal Hineinfunktionan die Menzel ist in Teile teils stehtmittlerweile mit dazwischen ?? ich war gerade das ist meine Funktionnicht einmal geschrieben habe teile diese Liste in zwei Teile das wäre KernbestandteilvonQuicksortund dann ruft diese Funktion sich selber aufsie nimmtdiese Liste hierund teilstdiese Liste in zwei Teileund diese Listenimmt sie her und teilt diese ist in zwei Teile indem sie sich selbst aufruftFunktion ruft sich selbst aufmit anderen Daten natürlich müssen die Daten immer einfacher werden Beistrich funktionierendie können nicht immer größere Listen haben sondern die wissentlich haben müssen immer kleiner werden?? Teile und herrsche aus allgemeiner Spruch eine Stelle teile und herrsche die Willi et ceterawie Caesarein großes Problem teilenund teilen und teilen damit du beherrschen das große Problemkann man auchin anderen Zusammenhängen verwenden als bei der Rekursion aber das ist definitiv ein Fall von Teile und herrsche diese kleinen Listenweiß ich wieder in mein Algorithmus muss dernoch kleinere Listen raus bautund so weiter und so fort bis zum Schluss der Fall eintritt das nichts mehr zu sortieren ist und der Algorithmus sagen kann ja jetzt weiß was es ist und dann geht das die ganze Kette wieder raufunddas ist die Ideehinter der Rekursionamübliche Witz an der Stelle ist deretwas dasim Informatikwörterbuchunterwegs ?? SchiffwillCursorim Informatikwörterbuchunter rekursivwenn sie denin der noch nicht okayda steht sie ?? Kursemüssen nicht drüber lachensonstiger Jahran andere Begriffe witzig dass sie natürliches eine Endlosschleife rekursiv sieheunter rekursivenwas nicht rekursiv ist im Sinneder Informatikanrekursiv kann nur funktionierendass sie deren Endlosschleiferekursiv sie rekursiv ist Endlosschleife das wäre nicht streng rekursiven Sinn Informatikrekursiv ist nurwenn ich ein kleineres Problem habeich gebe ein kleineres Problem zurückund dasmacht dasselbe noch mal mit ein noch kleiner Problem und so weiter und sofort hier das Problem nicht kleineraber sind üblich Informatikerwitzzum Thema rekursivanandere Art von Rekursion andere Anwender bei der Rekursion vorkommtzwei Personen oder Magister nehmen sie mit ?? Platz haben?? Dateisystemwenn ich einen Baum durchsuchevor das man Dateisystemein Ordner enthält ein Ordner enthälteinen weiteren Ordner und enthält Dateiensowasdieser Ordner enthälteinen Ordner und einen Ordner und Dateienein Teil so eine Dateidie Sorte enthält vielleicht nur Leerzeichennoch ?? Dateiund da es Leichtsammlungvon zwei Dateien drinund hier eine Datei drinwie durchsuche ich so ein Baumein Dateisystem was im Endeffekt ein Baum istsehr gernerekursivsie schreiben ein Programmdas eine Ebene kannSchreiben ein Programm das eine Ebene kann es kriegt einen Ordnerund durchsuchtwas in diesem Ordner ist an direkten Kinderund wenn es auf ein Ordner stößtmacht es wasdieses Programm wenn's auf einen Ordner stößt sich selbst wieder aufund durchsuchte dann diesen Ordner und die erste Ebenean Sachen da drinund für jeden Ordner bin ist darin findet ?? das Programm geschrieben ruft es sich selbst wieder aufauf der obersten Ebene sind das Programm wird für den Ordner aufgerufenfür jeden Ordnerdienstesfindet sich selbst wieder auf und so weiterganz klassische Anwendung von Rekursion ?? man Dateisystemedurchsuchen?? ich suche irgendeineneine Datei mit dem Text Blabla oder was auch immer wie machen Sie dasSchreiben an Programmdem sie ein Ort vergeben könnendas sich angucktwas in diesem Ordner drin stehtfür jeden Ort der drin steht und sich selbst aufdie Rolle von while-Schleifeüber alle Orte die da drin stehenund für jeden Text ?? da drin steht ob es wirklich nach Werbetextund damit hat fertig das ist sehr elegantund auch die übliche Lösung das zu tunalso wenn sie Bäume habenhaben sie sehr gerne auchRekursion