is Ben Rudgers

Remarks: Epigram 12

This is part of a writing exercise around Alan Perlis‘s Epigrams in Programming.

Recursion is the root of computation since it trades description for time.

When I first encountered this epigram my understanding of recursion was limited to recursive descriptions of procedures, not to recursive patterns of execution or recursive definitions of data structures.

The general pattern of recursive descriptions* I see in Lisp is:

  (defun foo (list 1)
         (let x (car list 1)
                (if (null x)
                      (bar x)
                      (foo (cdr list1))))))

Unsurprisingly, given that Lisp was conceived to explore recursion in Turing machines, there seems to be an intimate relationship between <code>cons, car, cdr</code> and recursive definitions. Because recursive description takes time out of the equation, there is one less thing to think about when considering Turing Machines and their equivalence.

The cons abstracts space, recursion time.

*Given optimization there is probably a bias toward tail calls when possible. Given the limited resources of early Lisp systems, the potential for optimization may have contributed toward this bias.