linux-l: [OT]: tail recursive

Guntram Trebs gunni at trebs.net
So Jul 22 13:47:27 CEST 2001


On Sun, 22 Jul 2001, Oliver Bandel wrote:

> Hallo,
>
> eine Frage an die Informatiker oder die andeen in
> theoretischer Informatik speziell gebildeten
> Leutchens: Was bedeutet "tail recursive"?
>
> Des öfteren treffe ich auf die Begriffe
> "recursive", "tail recursive" und "proper tail recursive".

Den Begriff habe ich noch nicht gehört, aber ich würde das so deuten,
dass der oder die rekursiven Aufrufe erst am Ende der aufgerufenen
Routine auftreten.

> Rekursivität ist  mir schon klar.
> Aber tail-recursive? Ich habe da zwar eine verschommene
> Vorstellung von, aber genau deswegen, weil das noch verschwommen
> ist, will ich das Bild gerne klären.
>
> BTW: Aus welchem Grunde soll man "tail-recursive"
> Algorithmen gewöhnlichen rekursiven Algorithmen vorziehen?
> (Soll schneller sein, zumindest mit FPLs - oder ist es bloß eleganter?)

Rekursive Prozesse haben zwei Nachteile:
 - es werden unter Umständen Dinge doppelt berechnet
 - man muss den Zustand speichern, bei dem die Rekursion auftrat


Wenn die Rekursion aber ganz am Ende auftritt, dann brauche ich
mir aber keinen Zustand zu speichern, denn dann muss ich ja nicht
mehr zurück. (Kann aber auch nicht mehr so einfach Funktionswerte
übergeben, falls ich das muss)

Soweit ich weiss, machen davon einige Prolog-Programme Gebrauch.

Dort wird das dann automatisch gemacht.

Bei einem Compiler müßtest Du wahrscheinlich selbst dafür sorgen.


Ausserdem gibt es noch eine andere Möglichkeit, die Platzprobleme
bei rekursiven Programmen zu beseitigen. Wenn Du nämlich den
Zustand in der aufrufenden Routine aus dem Zustand der aufgerufenen
Routine (eigentlich dieselben) zurückrechnen kannst, dann braucht Du ihn
nicht zu speichern.

Diese Optimierungen können allerdings, wenn nicht vom Compiler/Interpreter
ausgeführt, zu einem chaotischen Programmierstil führen.


Guntram


P.S.

auf google hast du ja sicherlich schon gesucht




Mehr Informationen über die Mailingliste linux-l