Writing GNU Emacs Extensions

Iterative List Functions

Recursion isn't always the right solution for a list-related programming problem. Sometimes plain old iteration is needed. In this example, we'll demonstrate the Emacs Lisp idiom for operating on a list of elements one at a time, sometimes called "cdr-ing down" a list (because in each iteration, the list is shortened by taking its cdr).

Suppose we need a function that counts the number of symbols in a list, skipping over other kinds of list elements like numbers, strings, and sublists. A recursive solution is wrong:

(defun count-syms (lst)
  (if (null lst)
      0
    (if (symbolp (car lst))
        (+ 1 (count-syms (cdr lst)))
      (count-syms (cdr lst)))))

Recursion—particularly deep recursion—introduces a fair amount of overhead in terms of keeping track of many nested function calls and return values, and should be avoided when possible. Furthermore, this problem naturally suggests an iterative solution, and code should usually reflect the natural approach to solving a problem, rather than obfuscating the solution by being too clever.

 (defun count-syms (lst)
   (let ((result 0))
     (while lst
       (if (symbolp (car lst))
           (setq result (+ 1 result)))
       (setq lst (cdr lst)))
     result))