When recurring on a list of atoms, lat, ask two questions about it: (null? lat) and else.
When recurring on a number, n, ask two questions about it: (zero? n) and else.
When recurring on a list of S-expressions, lst, ask three questions about it: (null? lst), (atom? (car lst)) and else.
The Second Commandment
Use cons to build lists.
The Third Commandment
When building a list, describe the first typical element, and then cons it onto the natural recursion.
The Fourth Commandment
Always change at least one argument while recurring. This must be done to get closer to termination.
When recurring on a list of atoms, lat, use (cdr lat).
When recurring on a number, n, use (sub1 n).
When recurring on a list of S-expressions, lst, use (car lst) and (cdr lst) if neither (null? lst) nor (atom? (car lst)) are true.
The changing argument must be tested in the termination condition.
When using cdr, test termination with null?.
When using sub1, test termination with zero?.
The Fifth Commandment
TODO
The Sixth Commandment
Simplify only after the function is correct.
The Seventh Commandment
Recur on the subparts that are of the same nature:
On the sublists of a list.
On the subexpressions of an arithmetic expression.
The Eighth Commandment
Use help functions to abstract from representations.
The Ninth Commandment
Abstract common patterns with a new function.
My Own Words
Recursive processes for building lists (or other recursive data structures) are OK, since the data structure is recursive in nature anyway.
Recursive processes for calculating numbers are not OK, since the value can be built iteratively, without wasting memory. Numbers tend to be much bigger than the length of a list in most practical examples. This means not using TCO will often result in high memory usage.
The law of car
The primitive car is defined only for non-empty lists.
The law of cdr
The primitive cdr is defined only for non-empty lists.
The cdr of any non-empty list is always another list.
