Рекурсивные функции, которые вызывают себя из хвостовой позиции, могут привести к переполнению стека; языковые реализации должны поддерживать некоторую форму исключения хвостового вызова , чтобы избежать проблемы.
Я избегал использования циклов для создания кода стиля lisp.
Common Lisp не требует, чтобы реализации выполняли исключение хвостовых вызовов, но реализации Scheme должны это делать. Идиоматия c в Scheme - использовать рекурсию для итерации, но в Common Lisp идиоматия c использовать другие итерационные устройства, если рекурсия не обеспечивает естественное решение проблемы.
Хотя Common Lisp реализации не требуются для исключения хвостовых вызовов, многие это делают. Clisp поддерживает ограниченное исключение хвостовых вызовов, но только в скомпилированном коде и только для саморекурсивных хвостовых вызовов. Это плохо документировано, но здесь можно найти некоторые обсуждения @ Renzo . Опубликованный код OP будет подлежать исключению хвостового вызова при компиляции в Clisp, поскольку функция alternatingSums вызывает себя из хвостовой позиции. Это охватывает большинство случаев, в которых вас может заинтересовать исключение хвостового вызова, но обратите внимание, что в этом случае устранение хвостового вызова выполняется не для взаимно рекурсивных определений функций в Clisp. См. Пример в конце этого ответа.
Определение функции из REPL или загрузка определения из исходного файла приведет к интерпретируемому коду. Если вы работаете в среде разработки, такой как SLIME, ее легко скомпилировать: из буфера исходного файла выполните команду Ctrl - c Ctrl - k , чтобы скомпилировать весь файл и отправить его в REPL, или поместите точку внутри или сразу после определения функции и выполните Ctrl - c Ctrl - c, чтобы скомпилировать одно определение и отправить его в REPL.
Вы также можете скомпилировать исходный файл перед его загрузкой, например, (load (compile-file "my-file.lisp")). Или вы можете загрузить исходный файл и скомпилировать функцию после этого, например (load "my-file.lisp"), затем (compile 'my-function).
Как уже упоминалось, более вероятно, что код idiomati c Common Lisp будет в любом случае не используйте рекурсию для такого рода функций. Вот определение с использованием макроса loop, которое некоторые сочли бы более ясным и кратким:
(defun alternating-sums (xs)
(loop for x across xs
and i below (length xs)
if (evenp i) sum x into evens
else sum x into odds
finally (return (list evens odds))))
Случай взаимно рекурсивных функций в Clisp
Вот простая пара взаимно рекурсивных определений функций:
(defun my-evenp (n)
(cond ((zerop n) t)
((= 1 n) nil)
(t (my-oddp (- n 1)))))
(defun my-oddp (n)
(my-evenp (- n 1)))
Ни одна из функций не вызывает себя напрямую, но my-evenp имеет вызов на my-oddp в хвостовой позиции, а my-oddp имеет вызов my-evenp в хвостовой позиции. Хотелось бы, чтобы эти хвостовые вызовы были устранены, чтобы избежать взрыва стека для больших входных данных, но Clisp этого не делает. Вот разборка:
CL-USER> (disassemble 'my-evenp)
Disassembly of function MY-EVENP
14 byte-code instructions:
0 (LOAD&PUSH 1)
1 (CALLS2&JMPIF 172 L16) ; ZEROP
4 (CONST&PUSH 0) ; 1
5 (LOAD&PUSH 2)
6 (CALLSR&JMPIF 1 47 L19) ; =
10 (LOAD&DEC&PUSH 1)
12 (CALL1 1) ; MY-ODDP
14 (SKIP&RET 2)
16 L16
16 (T)
17 (SKIP&RET 2)
19 L19
19 (NIL)
20 (SKIP&RET 2)
CL-USER> (disassemble 'my-oddp)
Disassembly of function MY-ODDP
3 byte-code instructions:
0 (LOAD&DEC&PUSH 1)
2 (CALL1 0) ; MY-EVENP
4 (SKIP&RET 2)
Сравните с хвостовой рекурсивной функцией, которая вызывает сама себя. Здесь нет вызова factorial при разборке, но вместо этого была вставлена инструкция перехода: (JMPTAIL 2 5 L0).
(defun factorial (n acc)
(if (zerop n) acc
(factorial (- n 1) (* n acc))))
CL-USER> (disassemble 'factorial)
Disassembly of function FACTORIAL
11 byte-code instructions:
0 L0
0 (LOAD&PUSH 2)
1 (CALLS2&JMPIF 172 L15) ; ZEROP
4 (LOAD&DEC&PUSH 2)
6 (LOAD&PUSH 3)
7 (LOAD&PUSH 3)
8 (CALLSR&PUSH 2 57) ; *
11 (JMPTAIL 2 5 L0)
15 L15
15 (LOAD 1)
16 (SKIP&RET 3)
Некоторые реализации Common Lisp поддерживают исключение хвостовых вызовов для взаимно рекурсивных функции. Вот разборка my-oddp из SBCL:
;; SBCL
; disassembly for MY-ODDP
; Size: 40 bytes. Origin: #x52C8F9E4 ; MY-ODDP
; 9E4: 498B4510 MOV RAX, [R13+16] ; thread.binding-stack-pointer
; 9E8: 488945F8 MOV [RBP-8], RAX
; 9EC: BF02000000 MOV EDI, 2
; 9F1: 488BD3 MOV RDX, RBX
; 9F4: E8771B37FF CALL #x52001570 ; GENERIC--
; 9F9: 488B5DF0 MOV RBX, [RBP-16]
; 9FD: B902000000 MOV ECX, 2
; A02: FF7508 PUSH QWORD PTR [RBP+8]
; A05: E9D89977FD JMP #x504093E2 ; #<FDEFN MY-EVENP>
; A0A: CC10 INT3 16 ; Invalid argument count trap
Это немного сложнее для чтения, чем в предыдущих примерах, потому что SBCL компилируется на язык ассемблера вместо байтового кода, но вы можете видеть, что инструкция перехода заменен звонок на my-evenp:
; A05: E9D89977FD JMP #x504093E2 ; #<FDEFN MY-EVENP>