Deep Recursion

• Flat recursion - looking at the elements of a container (sequence) data structure as atoms.
• Deep recursion - looking into the entire structure of the container considering that each element can be in turn a container.
• If the container is a list, the characteristics of deep recursion are:
• testing if the car of the list is also a list;
• calling itself recursively both on the car of the list and on the cdr of the list.

(defun count-top-level-symbols (L)
  " Counts all the symbols at the top level of the list using a flat recursion."
  (cond ((null L) 0)
        ((symbolp (car L))
         (+ 1 (count-top-level-symbols 
                  (cdr L))))
        (t (count-top-level-symbols 
                  (cdr L)))))

(count-top-level-symbols '((a b (c d) e) f g (h i (j)))) ; 2

(defun count-all-symbols (L)
  "Counts all symbols in the list L using deep recursion."
  (cond ((null L) 0)
        ((listp (car L))
         (+ (count-all-symbols (car L))
            (count-all-symbols (cdr L))))
        ((symbolp (car L))
         (+ 1 (count-all-symbols (cdr L))))
        (t (count-all-symbols (cdr L)))))

(count-all-symbols '((a b (c d) e) f g (h i (j)))) ;10

(defun depth (L)
  "Computes the depth of a list using deep recursion."
  (cond ((null L) 0)
        ((listp (car L))
         (max (+ 1 (depth (car L))) 
              (depth (cdr L))))
        (t (max 1 (depth (cdr L))))
   ))

(depth '((a b (c d) e) f g (h i (j)))) ; 3

Recursion Tree
A tree with a node for each recursive call and where the children of a node are the recursive calls it generates.