Exercise 2 Enter each of the following expressions into Scheme. In each case, explain why Scheme does or does not use the dot notation when displaying the value. Recursion with pair structures Just as lists can be nested within lists, so pairs can be nested within pairs, as deeply as you like. If we have a pair structure that is constructed by repeated invocations of cons , starting from constituents of some simple type such as numbers or strings, we can use pair recursion , which adapts the shape of the computation to the shape of the particular pair structure on which we operate. In pair recursion, the base cases are the values that are not pairs, and must therefore be operated on directly.
Every pair has exactly two components, and it is always valid to take the car and the cdr of a pair.
So the base case for a pair recursion is just any value that is not itself a pair. Every time the cons procedure is used, explicitly or implicitly, in the construction of a Scheme value, a new cons cell is allocated, to store information about the car and the cdr.