3. [erlang] : Warum ist tail recursion so viel effizienter als normale Rekursion was den Speicherverbrauch angeht?

[erlang] : Warum ist tail recursion so viel effizienter als normale Rekursion was den Speicherverbrauch angeht?

  • ?

    rüdiger schrieb:

    Tim schrieb:

    mngbd schrieb:

    erkurz schrieb:

    Hmm okay, das Umdenken ist dann bisschen doof für mich.

    Aber wohl auch nur, weil die meisten C(++)-Compiler solche naheliegenden Optimierungen nicht machen.

    Huch? Ist das so? Der gcc hat bei mir iirc immer tail-recursions wegoptimiert. Nicht dass ich ihn extra daraufhin getestet hätte.

    Wobei der GCC da wohl ein Experte ist. Andere Compiler (icc, suncc, msvc) machen das wohl nicht: http://dl.fefe.de/optimizer-isec.pdf (s.32)

    Ist das überhaupt richtig tail-recursive?

    0
  • K

    Tim schrieb:

    Ist das überhaupt richtig tail-recursive?

    Hmm, ich weiss auch nicht, was er mit der Folie sagen will. Die Fakultaetsfunktion ist nicht Endrekursiv (tail recursiv).

    0
  • ?

    Da kam der CCC in ihm durch und musste freie Software lobhudeln 🤡

    0
  • B

    Als Laie würde ich mal sagen, da steckt entweder ziemlich viel Magie in der gcc-Opti, oder sie haben eine spezielle Transformation für genau dieses Muster.

    0
  • ?

    rapso schrieb:

    Wenn man sichergehen will dass das gemacht wird, bleibt nichts anderes als ins disassembly zu schauen.

    Zumindest die glibc kann das bis zur Laufzeit transparent halten:
    http://www.gnu.org/s/libc/manual/html_node/Backtraces.html

    Bashar schrieb:

    Als Laie würde ich mal sagen, da steckt entweder ziemlich viel Magie in der gcc-Opti, oder sie haben eine spezielle Transformation für genau dieses Muster.

    Zumindest das Muster "Rekursion modulo primitive Operation, die keinen neuen Speicher anfordert" müsste man eigentlich immer in einen tail call + Akkumulator verwandeln können, oder?
    🙂

    0
  • M

    µngbd schrieb:

    Zumindest das Muster "Rekursion modulo primitive Operation, die keinen neuen Speicher anfordert" müsste man eigentlich immer in einen tail call + Akkumulator verwandeln können, oder?

    Bin auch Laie, aber das geht scheinbar wirklich so einfach. Unter den Einschränkungen, dass der Körper aus einem einzelnen if besteht, dass der Rekursionsabbruch im then-Teil ist, und dass nur das erste Argument bei der Rekursion verändert wird, geht das in Scheme zB so:

    (define (rec->tail fun-def)
  (let ((name (caadr fun-def))
        (first-arg (cadadr fun-def))
        (rest-args (cddadr fun-def))
        (if-expr (caddr fun-def)))
    (let ((test (cadr if-expr))
          (then-part (caddr if-expr))
          (else-part (cadddr if-expr)))
      (let ((operation (car else-part))
            (first-operand (cadr else-part))
            (new-arg (car (cdaddr else-part))))
        `(define ,(cons name (cons first-arg rest-args))
           (define (tail-rec ,first-arg acc)
             (if ,test
                 acc
                 (tail-rec ,new-arg (,operation ,first-operand acc))))
           (tail-rec ,first-arg ,then-part))))))

    Das geht natürlich mit der Fakultät:

    > (rec->tail '(define (fact n)
                (if (zero? n)
                    1
                    (* n (fact (- n 1))))))
(define (fact n)
  (define (tail-rec n acc) (if (zero? n) acc (tail-rec (- n 1) (* n acc))))
  (tail-rec n 1))

    Aber auch mit exotischeren Dingen, solange nur das erste Argument verändert wird:

    > (rec->tail '(define (fold lst proc init)
                (if (null? lst)
                    init
                    (proc (car lst)
                          (fold (cdr lst) proc init)))))
(define (fold lst proc init)
  (define (tail-rec lst acc)
    (if (null? lst) acc (tail-rec (cdr lst) (proc (car lst) acc))))
  (tail-rec lst init))

;; die beiden fold-Versionen reagieren gleich, zB:
(fold '(1 2 3 4) + 0)
(fold '(1 2 3 4) cons '())

    Heureka.
    🙂

    0
  • K

    Man kann jede Rekursion in eine Endrekursion mittels Continuation ueberfuehren. Manchmal geht es aber nicht immer mit einem einfachen Akkumulator, sondern man tauscht Stack gegen Heap.

    0
  • M

    knivil schrieb:

    Man kann jede Rekursion in eine Endrekursion mittels Continuation ueberfuehren.

    Ja, klar. Aber dazu muss man in jedem Durchlauf Closures erzeugen, was in manchen Sprachen nicht geht. Aber mein Muster geht immer.
    🙂

    0
  • K

    mngbd schrieb:

    Bin auch Laie ... Unter den Einschränkungen ... mein Muster geht immer

    Diese Argumentationskette kann ich nicht ganz nachvollziehen. 🙂 Nein, ich habe mir dein Schema noch nicht angesehen. Vielleicht magst du es mal auf die Tuerme von Hanoi anwenden (aber nicht nur fuer 3 Scheiben, sondern fuer beliebig viele).

    0
  • M

    knivil schrieb:

    mngbd schrieb:

    Bin auch Laie ... Unter den Einschränkungen ... mein Muster geht immer

    Diese Argumentationskette kann ich nicht ganz nachvollziehen. 🙂

    Hehe, da hast du recht. Ich hab dieses Muster gemeint, aber in allen mir bekannten Sprachen, die anderen Einschränkungen sorgen nur dafür, dass es genau so aussieht, und nicht zB <test> negiert und then-Teil & else-Teil vertauscht sind:

    (define (funktion x ...)
  (if <test>
      <letzter-wert-der-rekursion>
      (<operator> (funktion (<irgendwas> x) ...))))

    Das ist mir schon oft untergekommen. So könnte die magische tail recursion von Fefes gcc zustandekommen.

    knivil schrieb:

    Vielleicht magst du es mal auf die Tuerme von Hanoi anwenden (aber nicht nur fuer 3 Scheiben, sondern fuer beliebig viele).

    Mal nachsehen, aber ich fürchte, das wird nichts.
    🙂

    0
Anmelden zum Antworten