## 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.

```
(defun foo (list 1)
(let x (car list 1)
(if (null x)
nil
(progn
(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.