rekursiv

Adjektiv

Bedeutungen

1. durch sich selbst definierend, sich selbst aufrufend
   • Die Fakultätsfunktion wird gern als Paradebeispiel für eine rekursiv implementierte Funktion in den Vorlesungen vorgestellt.
   • Bei Linux-Befehlen, die rekursiv arbeiten, werden auch alle Unterverzeichnisse durchlaufen.
2. mehrfaches Auftreten gleicher Sprachformen
   • In einem Satz wie „Das schöne, sonnige, windige … Wetter gefällt mir“ liegt eine rekursive Struktur der Adjektive vor, die darin besteht, dass man hier (theoretisch nach Belieben) gleichgeordnete Adjektive aneinanderreihen kann.
   • Eine ähnliche rekursive Struktur kommt in der Wortbildung vor: „Ururur…oma“, „vorvorvor…gestern“ und viele andere mehr.
3. rekursive Produktion: eine Produktion (Ersetzungsregel) der Gestalt N→α, mit also dem Nichtterminalsymbol N, als linker Seite heißt rekursiv dann und nur dann, wenn die rechte Seite α, die Gestalt α=βNγ, hat.
   • Jede rekursive Produktion macht eine Grammatik trivialerweise rekursiv. Hingegen gibt es rekursive Sprachen, die keinerlei rekursive Produktionen enthalten müssen.
4. rekursive Grammatik: eine Grammatik G heißt rekursiv dann und nur dann, wenn sie ein Nichtterminalsymbol N, besitzt und eine Ableitung N⇒_G^*αNβ, zu einer Satzform αNβ,, die also dasselbe N, irgendwo enthält.