linux-l: [OT]: tail recursive

[Matthias Kranz]

On Sun, Jul 22, 2001 at 12:50:05PM +0200, Oliver Bandel wrote:
> eine Frage an die Informatiker oder die andeen in
> theoretischer Informatik speziell gebildeten
> Leutchens: Was bedeutet "tail recursive"?

end-rekursiv?

> Des öfteren treffe ich auf die Begriffe
> "recursive", "tail recursive" und "proper tail recursive".

Letzteren kenne ich noch gar nicht.

> Rekursivität ist  mir schon klar.

Prima.

> 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.

A call is tail-recursive if nothing has to be done after the the call
returns, i.e. when the call returns, the returned value is immediately
returned from the calling function.  In this example, the recursive call
to `myfun' is tail-recursive:
     
     (defun myfun (x)
       (if (oddp (random x))
           (isqrt x)
           (myfun (1- x))))

> 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?)

Nun, tail-rekursive Algorithmen lassen sich relativ einfach in iterative
Algorithmen uebertragen. Das machen "gute" Compiler sogar teilweise
selbst.

Ein einfaches Beispiel waere in etwa:

void tailRecursive(int n) {
    if (n > 0) {
        printf("Hicks.");
	tailRecursive(n-1);
    }
}

void interative(int n) {
    for (i = n; i > 0; i--)
        printf("Hicks.");
}

Iterative Algorithmen brauchen weniger Speicher. Iterative Algorithmen
haben den geringeren Berechnungsaufwand. Rekursive Algorithmen sind oft
intuitiver. Und schoener :)

Gruss,
Matthias
-- 
Matthias Kranz                                     mskranz at acm.org
                   http://www.belug.org/~kranz
ech`echo xiun|tr nu oc|sed 'sx\([sx]\)\([xoi]\)xo un\2\1 is xg'`ol