Помогите понять рекурсивную функцию в ANSI Common Lisp

Question

Что-то не могу понять, как работает данная функция из книги ANSI Common Lisp:

(defun our-length (lst)
  (if (null lst) ;; когда пустой возвращаем ноль
    0
    (+ (our-length (cdr lst)) 1))) ;; а это что?

Как, я могу сложить cdr списка и единицу?

Answer 1

our-length (cdr lst) - применяет функцию к хвосту списка. А уже к результату возврата добавляет единицу.

Допустим, в списке три элемента.

При первом вызове условие if (null lst) не выполняется. Происходит вызов our-length со списком в два элемента.

Условие опять не выполняется. Происходит вызов our-length со списком в один элемент.

И так до тех пор, пока не будет произведён вызов our-length с пустым списком. Тогда сработает условие и вернёт 0.

После чего станут проиходить возвраты из предыдущих вызовов. На кажом из них будет добавляться единица к результату.