[{"@context":"http:\/\/schema.org\/","@type":"BlogPosting","@id":"https:\/\/wiki.edu.vn\/wiki25\/2021\/09\/01\/rekursiver-datentyp-wikipedia\/#BlogPosting","mainEntityOfPage":"https:\/\/wiki.edu.vn\/wiki25\/2021\/09\/01\/rekursiver-datentyp-wikipedia\/","headline":"Rekursiver Datentyp \u2013 Wikipedia","name":"Rekursiver Datentyp \u2013 Wikipedia","description":"before-content-x4 Datentyp, der sich in seiner Definition auf sich selbst bezieht after-content-x4 In Computerprogrammiersprachen, a rekursiver Datentyp (auch bekannt als","datePublished":"2021-09-01","dateModified":"2021-09-01","author":{"@type":"Person","@id":"https:\/\/wiki.edu.vn\/wiki25\/author\/lordneo\/#Person","name":"lordneo","url":"https:\/\/wiki.edu.vn\/wiki25\/author\/lordneo\/","image":{"@type":"ImageObject","@id":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","height":96,"width":96}},"publisher":{"@type":"Organization","name":"Enzyklop\u00e4die","logo":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","width":600,"height":60}},"image":{"@type":"ImageObject","@id":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/c441aa78f783b3798a06b688e218f9801529388f","url":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/c441aa78f783b3798a06b688e218f9801529388f","height":"","width":""},"url":"https:\/\/wiki.edu.vn\/wiki25\/2021\/09\/01\/rekursiver-datentyp-wikipedia\/","wordCount":3035,"articleBody":"     (adsbygoogle = window.adsbygoogle || []).push({});before-content-x4Datentyp, der sich in seiner Definition auf sich selbst bezieht       (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4In Computerprogrammiersprachen, a rekursiver Datentyp (auch bekannt als a rekursiv definiert, induktiv definiert oder induktiver Datentyp) ist ein Datentyp f\u00fcr Werte, die andere Werte desselben Typs enthalten k\u00f6nnen.  Daten rekursiver Typen werden normalerweise als gerichtete Graphen betrachtet.Eine wichtige Anwendung der Rekursion in der Informatik ist die Definition dynamischer Datenstrukturen wie Listen und B\u00e4ume.  Rekursive Datenstrukturen k\u00f6nnen als Reaktion auf Laufzeitanforderungen dynamisch auf eine beliebig gro\u00dfe Gr\u00f6\u00dfe anwachsen;  Im Gegensatz dazu m\u00fcssen die Gr\u00f6\u00dfenanforderungen eines statischen Arrays zur Kompilierzeit festgelegt werden.Manchmal wird der Begriff “induktiver Datentyp” f\u00fcr algebraische Datentypen verwendet, die nicht unbedingt rekursiv sind.       (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4Table of ContentsBeispiel[edit]Gegenseitig rekursive Datentypen[edit]Isorekursive Typen[edit]\u00c4quikursive Typen[edit]Typisch synonym[edit]Siehe auch[edit]Beispiel[edit]Ein Beispiel ist der Listentyp in Haskell:data List a = Nil | Cons a (List a)Dies zeigt an, dass eine Liste von a’s entweder eine leere Liste oder a . ist Nachteile Zelle mit einem ‘a’ (dem “Kopf” der Liste) und einer weiteren Liste (dem “Ende”).Ein weiteres Beispiel ist ein \u00e4hnlicher einfach verlinkter Typ in Java:       (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4class List {    E value;    List next;}Dies zeigt an, dass eine nicht leere Liste des Typs E einen Datenmember des Typs E und einen Verweis auf ein anderes List-Objekt f\u00fcr den Rest der Liste enth\u00e4lt (oder einen Null-Verweis, um anzuzeigen, dass dies das Ende der Liste ist).Gegenseitig rekursive Datentypen[edit]Datentypen k\u00f6nnen auch durch gegenseitige Rekursion definiert werden.  Das wichtigste grundlegende Beispiel hierf\u00fcr ist ein Baum, der sich gegenseitig rekursiv im Sinne eines Waldes (einer Baumliste) definieren l\u00e4sst.  Symbolisch:f: [t[1], ..., t[k]]t: v fEin Wald F besteht aus einer Liste von B\u00e4umen, w\u00e4hrend ein Baum T besteht aus einem Wertpaar v und ein Wald F (seine Kinder).  Diese Definition ist elegant und abstrakt leicht zu handhaben (z. B. beim Beweis von S\u00e4tzen \u00fcber Eigenschaften von B\u00e4umen), da sie einen Baum in einfachen Worten ausdr\u00fcckt: eine Liste eines Typs und ein Paar von zwei Typen.Diese gegenseitig rekursive Definition kann in eine einfach rekursive Definition umgewandelt werden, indem die Definition einer Gesamtstruktur eingef\u00fcgt wird:t: v [t[1], ..., t[k]]Ein Baum T besteht aus einem Wertpaar v und eine Liste von B\u00e4umen (seine Kinder).  Diese Definition ist kompakter, aber etwas un\u00fcbersichtlicher: Ein Baum besteht aus einem Paar eines Typs und einer Liste eines anderen, die entwirrt werden m\u00fcssen, um Ergebnisse zu beweisen.In Standard ML k\u00f6nnen die Datentypen Baum und Gesamtstruktur wie folgt gegenseitig rekursiv definiert werden, was leere B\u00e4ume erm\u00f6glicht:datatype 'a tree = Empty | Node of 'a * 'a forestand      'a forest = Nil | Cons of 'a tree * 'a forestIn Haskell k\u00f6nnen die Baum- und Walddatentypen \u00e4hnlich definiert werden:data Tree a = Empty            | Node (a, Forest a)data Forest a = Nil              | Cons (Tree a) (Forest a)In der Typentheorie hat ein rekursiver Typ die allgemeine Form \u03bc\u03b1.T, wobei die Typvariable \u03b1 im Typ T vorkommen kann und f\u00fcr den gesamten Typ selbst steht.Zum Beispiel k\u00f6nnen die nat\u00fcrlichen Zahlen (siehe Peano-Arithmetik) durch den Haskell-Datentyp definiert werden:data Nat = Zero | Succ NatIn der Typentheorie w\u00fcrden wir sagen: neinT=\u03bc\u03b1.1+\u03b1{displaystyle nat=mualpha .1+alpha}  wobei die beiden Arme des Summentyps die Datenkonstruktoren Zero und Succ darstellen.  Zero nimmt keine Argumente an (also repr\u00e4sentiert durch den Einheitentyp) und Succ nimmt ein anderes Nat (also ein weiteres Element von \u03bc\u03b1.1+\u03b1{displaystyle mualpha .1+alpha}).Es gibt zwei Formen rekursiver Typen: die sogenannten isorekursiven Typen und die equirekursiven Typen.  Die beiden Formen unterscheiden sich darin, wie Terme eines rekursiven Typs eingef\u00fchrt und eliminiert werden.Isorekursive Typen[edit]Bei isorekursiven Typen ist der rekursive Typ \u03bc\u03b1.T{displaystyle mualpha .T}  und seine Erweiterung (oder abrollen) T[\u03bc\u03b1.T\/\u03b1]{displaystyle T[mu alpha .T\/alpha ]}  (Wo die Notation x[Y\/Z]{displaystyle X[Y\/Z]}  gibt an, dass alle Instanzen von Z in X durch Y ersetzt werden) unterschiedliche (und disjunkte) Typen mit speziellen Termkonstrukten sind, die normalerweise als bezeichnet werden rollen und abrollen, die einen Isomorphismus zwischen ihnen bilden.  Um genau zu sein: R\u00d6ll:T[\u03bc\u03b1.T\/\u03b1]\u2192\u03bc\u03b1.T{displaystyle roll:T[mu alpha .T\/alpha ]zu mualpha.T}  und dunR\u00d6ll:\u03bc\u03b1.T\u2192T[\u03bc\u03b1.T\/\u03b1]{displaystyle abrollen:mu alpha .Tto T[mu alpha .T\/alpha ]}, und diese beiden sind Umkehrfunktionen.\u00c4quikursive Typen[edit]Unter equirecursive Regeln ist ein rekursiver Typ \u03bc\u03b1.T{displaystyle mualpha .T}  und sein Abrollen T[\u03bc\u03b1.T\/\u03b1]{displaystyle T[mu alpha .T\/alpha ]}  sind gleich — das hei\u00dft, diese beiden Typausdr\u00fccke bezeichnen denselben Typ.  Tats\u00e4chlich gehen die meisten Theorien von equirecursiven Typen weiter und spezifizieren im Wesentlichen, dass zwei beliebige Typenausdr\u00fccke mit derselben “unendlichen Erweiterung” \u00e4quivalent sind.  Als Ergebnis dieser Regeln tragen equirecursive Typen wesentlich mehr Komplexit\u00e4t zu einem Typsystem bei als isorekursive Typen.  Algorithmische Probleme wie Typpr\u00fcfung und Typinferenz sind auch f\u00fcr equirecursive Typen schwieriger.  Da ein direkter Vergleich auf einem \u00e4quirekursiven Typ keinen Sinn macht, k\u00f6nnen sie in O(n log n)-Zeit in eine kanonische Form umgewandelt werden, die leicht verglichen werden kann.[2]Equirecursive Typen erfassen die Form von selbstreferentiellen (oder gegenseitig referenziellen) Typdefinitionen, die in prozeduralen und objektorientierten Programmiersprachen zu sehen sind, und treten auch in der typtheoretischen Semantik von Objekten und Klassen auf.  In funktionalen Programmiersprachen sind isorekursive Typen (in Form von Datentypen) weitaus h\u00e4ufiger.Typisch synonym[edit]Rekursion ist in Typsynonymen in Miranda, OCaml nicht erlaubt (es sei denn, -rectypes Flag verwendet wird oder es sich um einen Datensatz oder eine Variante handelt) und Haskell;  So sind beispielsweise die folgenden Haskell-Typen illegal:type Bad = (Int, Bad)type Evil = Bool -> EvilStattdessen muss es in einen algebraischen Datentyp eingeschlossen werden (auch wenn es nur einen Konstruktor hat):data Good = Pair Int Gooddata Fine = Fun (Bool -> Fine)Dies liegt daran, dass Typsynonyme, wie typedefs in C, zur Kompilierzeit durch ihre Definition ersetzt werden.  (Typsynonyme sind keine “echten” Typen; sie sind nur “Aliasnamen” f\u00fcr den Programmierer.) Aber wenn dies mit einem rekursiven Typ versucht wird, wird es endlos wiederholt, denn egal wie oft der Alias \u200b\u200bersetzt wird, er bleibt trotzdem bezieht sich auf sich selbst, zB “Bad” w\u00e4chst auf unbestimmte Zeit: Bad \u2192 (Int, Bad) \u2192 (Int, (Int, Bad)) \u2192 ... .Eine andere M\u00f6glichkeit besteht darin, dass eine Indirektionsebene (der algebraische Datentyp) erforderlich ist, damit das isorekursive Typsystem herausfinden kann, wann es rollen und abrollen.Siehe auch[edit]Dieser Artikel basiert auf Material aus dem Kostenloses Online-W\u00f6rterbuch der Informatik  vor dem 1. November 2008 und unter den “Neulizenzierungs”-Bedingungen der GFDL, Version 1.3 oder h\u00f6her, enthalten.     (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4"},{"@context":"http:\/\/schema.org\/","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"item":{"@id":"https:\/\/wiki.edu.vn\/wiki25\/#breadcrumbitem","name":"Enzyklop\u00e4die"}},{"@type":"ListItem","position":2,"item":{"@id":"https:\/\/wiki.edu.vn\/wiki25\/2021\/09\/01\/rekursiver-datentyp-wikipedia\/#breadcrumbitem","name":"Rekursiver Datentyp \u2013 Wikipedia"}}]}]