Как подсчитать все атомы в списке (или списке вложенных списков) при использовании рекурсии

Question

Я создаю рекурсивную функцию, которая подсчитывает количество атомов в списке. Он должен быть в состоянии сосчитать атомы списков, которые вложены. Например: (a (bc) ed) или (a (bc (ge)) ed), он должен считать b и c отдельно или b, c, e и d отдельно, а не как единое целое.

Это функция, которую я создал:

(defun  count-atoms (mylist)
    (cond
    ((null mylist) 0)
    ((listp (car mylist)) (count-atoms (car mylist)))
    ((atom (car mylist)) (+ 1 (count-atoms (rest mylist))))
    )
)

Выходное значение, которое я получаю, равно 3, но оно должно быть 5 (основано на (a (bc) ed)). Я предполагаю, что функция останавливается в тот момент, когда она достигает c. Как заставить функцию не останавливаться на c и вернуть ее к самому внешнему списку.

Answer 1

Вот способ, которым мы можем рассуждать о проблеме -

• Если ввод null, вернуть ноль

  '( )
    ^
    | 0 atoms 
  

• (индуктивный) В противном случае вход имеет хотя бы один элемент . Если car является списком, позвоните count-elements на car и cdr. Сложите два результата вместе и верните.

  '( a         b c d ... )
     ^         ^
     |         | count atoms in cdr <-
     |                                \
     | count atoms in sublist   <------\_ add together
  

• (индуктивный) В противном случае вход имеет по крайней мере один элемент, который не aсписок. Звоните count-elements на cdr. Добавьте один к результату и верните.

  '( a         b c d ... )
     ^         ^
     |         | count atoms in cdr <-
     |                                \
     | one atom      <-----------------\_ add together
  

Видите ли вы, чем отличается ваша программа?

Answer 2

Ваша ошибка в том, что вы игнорируете хвост во втором предложении.

(defun count-atoms (tree)
  "Count atoms in all leaves of the tree, ignoring terminating NIL."
  (if tree
      (+ (if (atom (car tree))
             1
             (count-atoms (car tree)))
         (count-atoms (cdr tree)))
      0))

сейчас

(count-atoms '(a (b c) e d))
==> 5
(count-atoms '(a (b c (g e)) e d))
==> 7
(count-atoms '(a (b c (g e)) nil e d))
==> 8