Allgemeine vs. strukturelle Rekursion

Hi,
ich verstehe den unterscheid zwischen allgemeiner und strukturelle Rekursion in Haskell nicht. Kann mir jmd den Unterschied erklären ?

Beispiele:


ebenfalls als allgemeine Rekursion gilt folgende Quicksort Implementierung:

Sieht für mich auf den ersten Blick gleich aus^^

Aber nur auf den ersten Blick, wie ich nach googlen erfahren habe.

Bei google nach "strukturelle rekursion" habe ich
Einführung in die Informatik: 18 Generative Rekursion gefunden.

Allgemeine Rekursion scheint einfach "allgemeiner" zu sein:

Bisher: Funktionsdenition durch Muster für induktive Datentypen (strukturelle Rekursion)
Jetzt: Verallgemeinerung zu generativer (allgemeiner) Rekursion
- keine direkte Anlehnung an einen Datentyp
- keine Terminationsgarantie

Zum Vergrößern anklicken....

Das mit den beliebigen Datentypen könnte man auch dein quicksort-Beispiel übertragen, oder? Also einfach nur listen mit beliebigem Inhalt
Bei der quersumme trifft das natürlich nicht zu (Int -> Int).

Terminationsgarantie? Beim ersten schon - beim 2ten ka. Es mangelt an meinen Haskell-Kenntnissen^^ Wir hatten Scheme..
Beim dritten? Sieht auf den ersten Blick terminierend aus, oder? Zumindes sind alle Eingabefälle abgedeckt?
Das vierte sollte aber eigtl. auch terminieren..

Sonst link doch mal dein Skript? Evtl versteht man in eurer Vorlesung bischen was anderes unter den Begriffen. Kann mich garnicht erinnern, dass wir sowas mal unterschieden haben.

Die einzige besondere Art von Rekursion (Tail-Rekursion) die bei uns extra erwähnt wurde ist das, was asdfman hier vormacht:
Rekusiv und iterativ bezüglich Sortieralgorithmen..

Die "strukturelle Rekursion" ist letztlich ein Induktionsverfahren, bei dem das Ergebnis der Funktion für einen Wert definiert ist über das Ergebnis für einen kleineren Wert (i-1, das xs aus x:xs) (für eine sehr allgemeine Bedeutung des Wortes "kleiner" -> Listenlänge z.B.). Dadurch ist auch die Terminierung garantiert, da man irgendwann beim kleinsten Element angekommen ist (0, [] etc.). Bei der allgemeinen Rekusion gibt es kein solches Muster und deswegen im allgemeinen auch keine Terminierungsgarantie, auch wenn die Quersummenfunktion natürlich terminiert.

Ich finde es ja verdammt ärgerlich, wie OP immer seine Hausaufgaben hier gemacht bekommen will und wenn
sich dann jemand gefunden hat, der ihm hilft, bedankt er sich nicht einmal.