In this problem we begin to study deep recursion. In most of our previous recursive procedures we have dealt with the top-level elements of a list, whether or not those elements were themselves lists or symbols. Most algorithms on lists implemented so far have enumerated the elements of the list by performing a recursive call only on the cdr of the list. This is sometimes referred to as cdr-ing down the list. We now wish to consider whether the car of a list is a pair and if so, we will make a recursive call on the car of the list as well as the the cdr of the list. This approach is sometimes referred to as deep recursion .

In this problem you are asked to develop a procedure:

(define count-all-items

(lambda (item list)

...))

which will count the number of appearances of the symbol item in list. Your procedure should be deeply recursive, that is, it should count each appearance of item in each level of list.

Analyze the performance of your count-all-items procedure. What is order of comparison operations as a function ot the number of items in the list?