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