Material to Understand

• A recursive function is a function that calls itself one or more times within its body.
• A recursive function is tail-recursive, if when the base case is hit, the answer is known and no more computation needs to be done in the unwinding of the recursion. Tail recursion is very good in Common Lisp because the compiler will detect it and automatically translate the code into an iterative construct.
• One common form of recursion is rest recursion.

    (defun my-reverse (alist)
      (if (null alist)
          nil 
          (append (my-reverse (rest alist)) (list (first alist)))
      )
    )
  

• Another common form of recursion is first/rest recursion.

    (defun reverse-all (alist)
      (cond
        ((null alist) nil)
        ((atom alist) alist)
        (t (append (reverse-all (rest alist)) (list (reverse-all (first alist)))))
      )
    )
  

• It is possible to use optional parameters.

    (defun add (n &optional (m 0))   ;; if m is not supplied, it is 0
      (+ n m)
    )
  
    (add 10)        ;; one way to call the above function
    (add 10 5)      ;; another way
  

• It is possible to use rest parameters.

    (defun how-many (&rest numbers)
      (length numbers)
    )
  
    (how-many 1)
    (how-many 1 2)
    (how-many 1 2 3)    ;; Cool, huh?
  

• It is possible to use keyword parameters.

    (defun add (&key (number1 0) (number2 0))
      (+ number1 number2)
    )
    
    (add)
    (add :number1 5)
    (add :number1 5 :number2 10)
    (add :number2 10 :number1 5)
  

Exercises

1. Develop a recursive function called my-count that computes the number of times that an atomic key appears as a top-level element in a list. For example, (my-count '(1 2 (3 1) 1) 1) should return a 2 because the atomic key 1 appears as a top level element twice in the list '(1 2 (3 1) 1).
2. Once the function above is working, trace it, and run it again to make sure that you understand the recursion. To trace the function, type (trace my-count)
3. Make function my-count tail-recursive. The tail-recursive version should have an optional parameter.
4. Once the function above is working, trace it.
5. Change function my-count so that it counts all occurrences of the key. For example, (my-count '(1 2 (3 1) 1) 1) should now return a 3.
6. Again, trace the function once it is working and make sure that you understand the recursion. Have John take a look at your function to see if there are any improvements that can be made.
7. Define user-defined-list to do what the primitive list does. Use a rest parameter.
8. Define my-nthcdr, a function that uses a keyword parameter with a default value of 1. Do not use nthcdr in the function body!