Process vs. Procedure Recursion

Just because a procedure is recursive, doesn’t mean the process that it generates is recursive. A procedure is recursive when that procedure refers to itself in order to evaluate.

(defn factorial [x]
  (letfn [(fact-iter [product counter max-count]
    (if (> counter max-count)
      product
      (fact-iter (* counter product)
                 (inc counter)
                 max-count))
    )]
    (fact-iter 1 1 n))  
  )

fact-iter, in the above code, is a recursive procedure, but the process it generates is not recursive. A recursive process is characterized by a “chain of deferred operations.” The process generated by fact-iter, however, has no such chain of deferred operations. Rather, it is an iterative process, a process whose state is captured with variables, along with rules that describe how to move from one state to the next.

Iterative processes generated by recursive procedures are possible in Lisp because Lisp implements tail-recursion. Because of this, Lisp does not need special looping constructs.

From pgs. 42-43