(require 'stdlib)
;;What is tail recursion?
;;The most efficient type of recursion.
;;A function is called tail-recursive, if it is a continuation of
;;itself. In other words, it is tail-recursive, if the last function it
;;applies before returning is itself, as in the following example:
;;(DEFUN F(A)
;; (COND ((NULL A) T) ; END OF LIST: RETURN T
;; ((EQ (CAR A) *F*) *F*) ; *F* FOUND: RETURN *F*
;; (T (F (CDR A))))) ; F APPLIES ITSELF BEFORE RETURNING
;;Since F returns immediately after applying itself, there is no need to
;;return to F before returning from F. Instead, F can branch to its own
;;beginning and save a complete function call. Thereby, the program is
;;transformed into something like
;;(DEFUN F(A)
;; (COND ((NULL A) T) ; END OF LIST: RETURN T
;; ((EQ (CAR A) *F*) *F*) ; *F* FOUND: RETURN *F*
;; (T (PROG
;; (SETQ A (CDR A)) ; CHANGE A IN SITU
;; (GOTO F))))) ; LOOP
;;Additional definitions:
;;(PROG A B ...) evaluates its arguments in the given order.
;;(SETQ A EXPR) binds EXPR to the symbol A.
;;(GOTO F) performs a branch to the function F (normally it branches to
;;a LABEL rather than a function).
;;Properly tail-recursive implementations of LISP perform this
;;transformation automatically, so that tail-recursive code may be used
;;to implement iterations.
(define (sum-tail n)
"will take any N > 0, add time, stir."
(define (sum-tail-intern n sum)
(cond ((eq n 0) sum)
(t (sum-tail-intern (1- n) (+ n sum)))))
(sum-tail-intern n 0))
(define (sum-no-tail n)
"will crap out as soon as the stack is burnt up."
(cond ((eq n 0) 0)
(t (+ n (sum-no-tail (1- n))))))