CP104 Lecture Notes - Lecture 2: Insertion Sort, Association List, Natural Number
2
CP104 Full Course Notes
Verified Note
2 documents
Document Summary
We can extend the idea of a self-referential definition to defining the natural numbers, which leads to the use of recursion in order to write functions that consume numbers. The analogy to the self-referential definition of lists can be made clearer by defining a 1 plus function (define (add1 n) (+ 1 n)) (add1 0) => 1 (add1 (add1 0)) => 2 (add1 (add1 (add1 0))) => 3. Empty? distinguishes between the base case and the recursive case. Cons makes a list that is one step farther from the base case. Rest makes the list formed by undoing the cons. First is what you take away from a list to get the rest. 0 is the base case zero? distinguishes between the base case and the recursive case add1 makes a number that is one step farther from the base case. Rest makes the number formed by undoing the add1. First is 1 (define (sub1 n) (- n 1))
