Как понять рекурсию Common Lisp?

Question

Вот сама функция копирования списка:

(defun my-copy-list (lst)
   (if (atom lst)
       lst
       (cons (car lst) (my-copy-list (cdr lst)))))

A trace выдает мне такой код:

 CL-USER> (our-copy-list '(a b c))                                                 
| 7  0: (OUR-COPY-LIST (A B C))                                                      
| 8    1: (OUR-COPY-LIST (B C))                                                      
| 9      2: (OUR-COPY-LIST (C))                                                      
|10        3: (OUR-COPY-LIST NIL)                                                    
|11        3: OUR-COPY-LIST returned NIL                                             
|12      2: OUR-COPY-LIST returned (C)                                               
|13    1: OUR-COPY-LIST returned (B C)                                               
|14  0: OUR-COPY-LIST returned (A B C)                                               
|15(A B C)

Правильно ли я понял? Cписок уменьшается на один элемент спомощью cdr, затем сработало условие if (atom lst) - функция встретила nil и вернула его в качестве значения. После этого шага, я не понимаю. Как здесь работает cons? Она берет car lst, но trace показывает, что список начинает наращиватся с последнего элемента!

Answer 1

но trace показывает, что список начинает наращиватся с последнего элемента!

trace в этом случае сначала показывает внутренние вызовы функции, а потом внешние. То есть в обратном порядке по сравнению с тем, как они вызывались.

Давайте по шагам рассмотрим, что здесь происходит. Я буду использовать номера от 7 до 14 из вашего результата trace, так как они очень удобные.

В строке 7 самое начало — мы вызвали функцию:

(our-copy-list '(a b c))

В строке 8 функция из строки 7 вызвала cons, но в качестве второго аргумента вызвала себя же (но с другим аргументом). Мы сначала рассчитываем внутреннюю функцию (так как мы не можем сделать cons, пока не узнаем, что именно будет cons'ить, а для этого надо посчитать внутреннюю функцию).

Поэтому Лисп откладывает cons где-то в памяти в стеке, а переходит к рассмотрению внутреннней функции our-copy-list:

(cons 'a (our-copy-list '(b c)))

В строке 9 уже внутренняя функция вызвала ещё более глубокую функцию. (trace подсказывает нам, что это второй уровень вложенности, числом 2:). Так что внутренний cons тоже записываем в памяти, а всё внимание сосредатачиваем на внутреннем our-copy-list:

(cons 'a 
      (cons 'b (our-copy-list '(c))))

И эта вложенная функция снова сделала то же самое — вызвала себя же. Это видно в строке 10. Снова запоминаем cons'ы в стеке (сейчас у нас там запомнено три cons'а) и всё внимание обращаем на our-copy-list:

(cons 'a 
      (cons 'b
            (cons 'c (our-copy-list NIL))))

А вот здесь, на строке 11, (our-copy-list NIL) наконец-то вернёт значение! Им будет nil. Мы можем подставить его в cons:

(cons 'a 
      (cons 'b
            (cons 'c NIL)))

Теперь мы знаем, что вернёт внутренний (cons 'c NIL) — он вернёт список из одного элемента, символа c. Условно я обозначу его в схеме '(c) — но тут есть подвох. Список, созданный с помощью (cons 'c NIL) можно изменять — это нам обещает стандарт Лиспа. А вот про список '(c) таких обещаний нам стандарт никто не даёт.

Но для простоты напишем '(c).

Итак, в строке 12 мы уже знаем результат (cons 'c NIL):

(cons 'a 
      (cons 'b '(c)))

Теперь в строке 13 мы можем посчитать (cons 'b '(c)) (он будет равен списку, примерно равному '(b c), но, в отличие от '(b c), стандарт даёт право его изменять) и подставить его во внешнюю функцию:

(cons 'a '(b c))

И вот наконец на строке 14 мы можем посчитать значение самого первого cons'а:

'(a b c)

Это и будет наш результат (с поправкой на то, что '(a b c) — это условное обозначение: новосозданный список можно изменять, а вот как будет работать '(a b c) при изменении — никто не гарантирует, зависит от реализации).

БЛОГ НА HUSL

Как понять рекурсию Common Lisp?

Ответы (1 шт):