Oft weiß man nicht von Anfang an wie viele Elemente man abarbeiten muss. Deshalb kann man diese auch nicht in einem statischem Datentyp speichern, sondern man muss auf dynamische Datentypen zurückgreifen. Bei diesen kann man die Anzahl der Elemente auch zu Laufzeit problemlos ändern. Solche Datentypen sind zum Beispiel Listen.
Diese Strukturen werden auch als rekursive Datenstrukturen bezeichnet, weil jedes Element in der Liste eine Instanz zu seinem Nachbarn hat. Jedes Element kennt als das Element “rechts” neben ihm (wo auch immer rechts sein mag). Dabei ist darauf zu achten, das es einen speziellen Wert gibt, den nur das letzte Element besitzt um zu signalisieren das es kein Element mehr nach ihm gibt.
Rekursion umgangssprachlich beschrieben:
Irgendwo in der eigenen Definition (z.B. Listen(-feld)- oder Funktionsdefinition) ist ein Verweis auf mich selbst, oder auf etwas gleichen Typs.
Eine Liste erstellen
Eine Liste wird ähnlich wie eine Variable definiert:
(define liste
(cons 'element1 (cons 'element2 empty)))
Wir haben also eine Liste mit dem Name liste erstellt mit 2 Elementen. Das dritte Element empty ist das oben erwähnte Element welches signalisiert das das Ende der Liste erreicht wurde. Die Funktion cons (engl. construct) erwartet immer 2 Parameter: Der Erste ist das Element was man an die Liste anfügen will, und im 2. Parameter kann man entweder das nächste Listenelement anhängen oder man setzt das empty Element.
Man kann jeden beliebigen Datentyp in der Liste speichern, auch gemixt – und auch neue eigenständige Listen. Zum Beispiel kann das erste Element ein Symbol, das Zweite eine Zahl, das Dritte ein String usw. sein. Es ist bloß wichtig darauf zu achten, dass man prüft welchen Typs das aktuelle Element ist, bevor man es verwendet.
Es gibt noch eine weitere Möglichkeit eine Liste zu erstellen, und zwar mit der Funktion list:
(list 52 'hallo liste 'und 'so 'weiter)
Der Funktion list kann man beliebig viele Parameter übergeben, auch der Typ ist egal!
Nächster Bitte!
Stellen wir uns die Liste die wir erstellt haben nun bildlich vor:
| 'element1 |---->| 'element2 |----> empty
Mit Scheme kann man nur auf das erste Element (first) der Liste zugreifen.
(first liste) -> 'element1
Hier sehen wir wie man auf das erste Element in der vorhin definierten Liste zugreift. Dabei gibt die Funktion das entsprechende Symbol ‘element1 zurück.
Will man auf das zweite, oder irgendein anderes Element zugreifen so überspringt man das Element davor. Dazu gibt es die Funktion rest. Wenn man die Prozedur rest auf eine Liste anwendet, wird das erste Element der Liste fallen gelassen und alle übrig geblieben Elemente sind die neue Liste.
(define neue-liste (rest liste))
Die neue Liste sieht also so aus:
Jetzt kann man mit first auf das vormals Zweite, jetzt aber erste Element zugreifen.
empty?
Man kann die Prozedur rest ein weiteres mal auf die Liste neue-liste anwenden, dann zeigt das erste Listenelement aber auf empty – die Liste ist also leer. Wenn man jetzt versucht mit first auf das Element zuzugreifen gibt es einen Fehler!
Damit das nicht passiert gibt es so genannte Prädikate.
Mit der Funktion empty? kann man abfragen ob das aktuelle Element das spezielle empty Element ist.
(empty? (rest neue-liste)) -> true
andere Prädikate
Es gibt noch eine Menge anderer Prädikate. Zum Beispiel hat jeder Datentyp sein eigenes.
(symbol? 'test) -> true
(symbol? 42) -> false
(list? liste) -> true
).
mal aufgerufen wird. Nach 
.
und 
. f ist also in O(g(n)), wenn auch erst ab einen 
. Man untersucht das Verhalten wenn n gegen unendlich geht (
sind nur + und *, denn es ist nicht möglich den Zahlenbereich von natürlichen Zahlen verlassen. Mit den Operationen – oder / kann man den Zahlenbereich aber verlassen, d.h. sie sind nicht abgeschlossen.