Next: , Previous: , Up: Local Call   [Contents][Index]


5.6.4 Local Tail Recursion

Tail-recursive local calls are particularly efficient, since they are in effect an assignment plus a control transfer. Scheme programmers write loops with tail-recursive local calls, instead of using the imperative go and setq. This has not caught on in the Common Lisp community, since conventional Common Lisp compilers don’t implement local call. In Python, users can choose to write loops such as:

(defun ! (n)
  (labels ((loop (n total)
             (if (zerop n)
                 total
                 (loop (1- n) (* n total)))))
    (loop n 1)))
Macro: extensions:iterate name ({(var initial-value)}*) {declaration}* {form}*

This macro provides syntactic sugar for using labels to do iteration. It creates a local function name with the specified vars as its arguments and the declarations and forms as its body. This function is then called with the initial-values, and the result of the call is return from the macro.

Here is our factorial example rewritten using iterate:

    (defun ! (n)
      (iterate loop
               ((n n)
               (total 1))
        (if (zerop n)
          total
          (loop (1- n) (* n total)))))
  

The main advantage of using iterate over do is that iterate naturally allows stepping to be done differently depending on conditionals in the body of the loop. iterate can also be used to implement algorithms that aren’t really iterative by simply doing a non-tail call. For example, the standard recursive definition of factorial can be written like this:

(iterate fact
         ((n n))
  (if (zerop n)
      1
      (* n (fact (1- n)))))