Source code: Recursividad Terminal (Tail Recursion)

Código fuente Lisp sobre Recursividad Terminal

Ver la entrada correspondiente en el siguiente enlace:

Recursividad Terminal (Tail Recursion)

;Normal recursion
(defun my_reverse (a_list)
    (cond
        ((null a_list) nil)
        (t (append
                (my_reverse (rest a_list))
                (list (first a_list))
           ) 
        )
    )
)

;(trace my_reverse)
(write (my_reverse '(1 2 3 4 5)))
(write-line "")


;Tail recursion
(defun my_reverse_tail_inner (in_list out_list)
    (cond
        ((null in_list) out_list)
        (t (my_reverse_tail_inner
                (rest in_list)
;Alternativa al append.
;                (cons (first in_list) out_list)
                (append
                    (list (first in_list))
                    out_list
                )
            )
        )
    )
)

(defun my_reverse_tail (a_list)
    (my_reverse_tail_inner a_list nil)
) 

;(compile 'my_reverse_tail_inner)
;(trace my_reverse_tail_inner)
;(trace my_reverse_tail)
(write (my_reverse_tail '(1 2 3 4 5)))
(write-line "")

(compile 'my_reverse)
(compile 'my_reverse_tail_inner)

;normal: se desborda la pila con menos de 35000 elementos.
(time (write (list-length (my_reverse (loop for n from 1 to 34000 by 1 collect n)))))
(write-line "")

;terminal con tantos elementos como la normal.
(time (write (list-length (my_reverse_tail (loop for n from 1 to 34000 by 1 collect n)))))
(write-line "")

;terminal: prueba de que se puede utilizar con una cantidad de elementos enorme.
(time (write (list-length (my_reverse_tail (loop for n from 1 to 3400012 by 1 collect n)))))
(write-line "")