-
First
- When recurring on a list of atoms, lat, ask two questions about it: (null? lat) and else
- when recurring on a number, n, always two questions: (zero? n) and else
- When recurring on a list of S-expressions, l, ask three questions about it: (null? l), (atom? (car l)), and else
- Second: use cons to build lists
- Third: when building a list, describe the first typical element, and then cons it onto the natural recursion
-
Fourth
-
always change at least 1 argument when recurring. It must be changed to be closer to termination.
- When recurring on a number n, use (sub1 n)
- When recurring on a list of atoms, lat, use (cdr lat)
- When recurring on a list of S-expressions, l, use (car l) and (cdr l) if neither (null? l) nor (atom? (car l)) 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?.
-
Fifth
- When building a value with +, always use 0 for the value of the termination line, since 0 does not change the value of an addition
- When building a value with *, always use 1 for the value of the termination line, since 1 does not change the value of a multiplication
- When building a value with cons, always consider () for the value of the termination line
- Six: simplify only after the function is correct
-
Seventh: recur on the subparts that are of the same nature
- On the sublists of a list
- On a subexpressions of an arithmetic expression
- Eighth: use help functions to abstract from representations
- Ninth: abstract common patterns with an new function.
- Tenth: build functions to collect more than one value at a time