尾递归函数还能得到堆栈溢出吗？
Can a tail recursive function still get stack overflow?
我一直在 codesignal.com 解决一些挑战，使用 C-Lisp 来学习它，并且我一直在避免使用循环来制作 lisp 风格的代码。
在这个名为 alternatingSums 的挑战中（它给你一个可以非常大的 int 数组 a 并要求你 return 一个 array/list {sumOfEvenIndexedElements, sumOfOddIndexedElements}）我一直收到堆栈溢出此代码错误：
(defun alternatingSums(a &optional (index 0) (accumulated '(0 0)))
(cond ((= index (length a))
accumulated)
((evenp index)
(alternatingSums
a
(1+ index)
`(,(+ (svref a index ) (elt accumulated 0)) ,(elt accumulated 1)))
)
((oddp index)
(alternatingSums
a
(1+ index)
`(,(elt accumulated 0) ,(+ (svref a index ) (elt accumulated 1))))
)
)
)
它不是尾递归的还是尾递归函数仍然会出现堆栈溢出？
Common Lisp 编译器不需要优化尾调用。很多都这样做，但并非所有实现都默认编译您的代码；您必须使用 compile-file 编译文件，或者使用 (compile 'alternatingsums).
单独编译函数
CLISP 包含一个解释器（处理 Lisp 源代码的嵌套列表表示）和一个字节码编译器。编译器支持尾递归，而解释器不支持：
$ clisp -q
[1]> (defun countdown (n) (unless (zerop n) (countdown (1- n))))
COUNTDOWN
[2]> (countdown 10000000)
*** - Program stack overflow. RESET
[3]> (compile 'countdown)
COUNTDOWN ;
NIL ;
NIL
[4]> (countdown 10000000)
NIL
深入了解一下：
[5]>（反汇编'倒计时）
Disassembly of function COUNTDOWN
1 required argument
0 optional arguments
No rest parameter
No keyword parameters
8 byte-code instructions:
0 L0
0 (LOAD&PUSH 1)
1 (CALLS2&JMPIF 172 L10) ; ZEROP
4 (LOAD&DEC&PUSH 1)
6 (JMPTAIL 1 3 L0)
10 L10
10 (NIL)
11 (SKIP&RET 2)
NIL
我们可以看到虚拟机有一个JMPTAIL原语。
尾调用的另一种方法是通过宏。多年前，我破解了一个 macro called tlet，它可以让你使用类似于 labels 的语法定义（看起来像什么）词法函数。 tlet 构造编译成 tagbody 形式，其中函数之间的尾调用是 go 形式。它不分析位于尾部位置的调用：所有调用都是无条件传输，无论它们在语法中的位置如何，都不会 return 。同一个源文件还提供了基于蹦床的全局函数间尾调用的实现。
这是 CLISP 中的 tlet；注意：该表达式尚未编译，但它不会 运行 出栈：
$ clisp -q -i tail-recursion.lisp
;; Loading file tail-recursion.lisp ...
;; Loaded file tail-recursion.lisp
[1]> (tlet ((counter (n) (unless (zerop n) (counter (1- n)))))
(counter 100000))
NIL
tlet 不是优化器。对 counter 的调用在语义上总是一个 goto；它不是在适当的情况下有时会变成 goto 的过程调用。观察当我们添加 print:
时会发生什么
[2]> (tlet ((counter (n) (unless (zerop n) (print (counter (1- n))))))
(counter 100000))
NIL
没错；没有什么！ (counter (1- n)) 永远不会 returns，所以 print 永远不会被调用。
从尾部位置调用自身的递归函数会导致堆栈溢出；语言实现必须支持某种形式的 tail call elimination 才能避免此问题。
I've been avoiding using loops to make lisp style code.
Common Lisp 不要求实现执行尾调用消除，但 Scheme 实现必须这样做。在 Scheme 中，使用递归进行迭代是惯用的，但在 Common Lisp 中，使用其他迭代设备是惯用的，除非递归为手头的问题提供了自然的解决方案。
虽然 Common Lisp 实现不需要进行尾调用消除，但很多实现都需要。 Clisp 确实支持有限的尾调用消除，但仅限于编译后的代码，并且仅适用于自递归尾调用。这没有很好的记录，但是 there is some discussion to be found here 。 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)。
如前所述，惯用的 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>
我一直在 codesignal.com 解决一些挑战，使用 C-Lisp 来学习它，并且我一直在避免使用循环来制作 lisp 风格的代码。
在这个名为 alternatingSums 的挑战中（它给你一个可以非常大的 int 数组 a 并要求你 return 一个 array/list {sumOfEvenIndexedElements, sumOfOddIndexedElements}）我一直收到堆栈溢出此代码错误：
(defun alternatingSums(a &optional (index 0) (accumulated '(0 0)))
(cond ((= index (length a))
accumulated)
((evenp index)
(alternatingSums
a
(1+ index)
`(,(+ (svref a index ) (elt accumulated 0)) ,(elt accumulated 1)))
)
((oddp index)
(alternatingSums
a
(1+ index)
`(,(elt accumulated 0) ,(+ (svref a index ) (elt accumulated 1))))
)
)
)
它不是尾递归的还是尾递归函数仍然会出现堆栈溢出？
Common Lisp 编译器不需要优化尾调用。很多都这样做，但并非所有实现都默认编译您的代码；您必须使用 compile-file 编译文件，或者使用 (compile 'alternatingsums).
CLISP 包含一个解释器（处理 Lisp 源代码的嵌套列表表示）和一个字节码编译器。编译器支持尾递归，而解释器不支持：
$ clisp -q
[1]> (defun countdown (n) (unless (zerop n) (countdown (1- n))))
COUNTDOWN
[2]> (countdown 10000000)
*** - Program stack overflow. RESET
[3]> (compile 'countdown)
COUNTDOWN ;
NIL ;
NIL
[4]> (countdown 10000000)
NIL
深入了解一下：
[5]>（反汇编'倒计时）
Disassembly of function COUNTDOWN
1 required argument
0 optional arguments
No rest parameter
No keyword parameters
8 byte-code instructions:
0 L0
0 (LOAD&PUSH 1)
1 (CALLS2&JMPIF 172 L10) ; ZEROP
4 (LOAD&DEC&PUSH 1)
6 (JMPTAIL 1 3 L0)
10 L10
10 (NIL)
11 (SKIP&RET 2)
NIL
我们可以看到虚拟机有一个JMPTAIL原语。
尾调用的另一种方法是通过宏。多年前，我破解了一个 macro called tlet，它可以让你使用类似于 labels 的语法定义（看起来像什么）词法函数。 tlet 构造编译成 tagbody 形式，其中函数之间的尾调用是 go 形式。它不分析位于尾部位置的调用：所有调用都是无条件传输，无论它们在语法中的位置如何，都不会 return 。同一个源文件还提供了基于蹦床的全局函数间尾调用的实现。
这是 CLISP 中的 tlet；注意：该表达式尚未编译，但它不会 运行 出栈：
$ clisp -q -i tail-recursion.lisp
;; Loading file tail-recursion.lisp ...
;; Loaded file tail-recursion.lisp
[1]> (tlet ((counter (n) (unless (zerop n) (counter (1- n)))))
(counter 100000))
NIL
tlet 不是优化器。对 counter 的调用在语义上总是一个 goto；它不是在适当的情况下有时会变成 goto 的过程调用。观察当我们添加 print:
[2]> (tlet ((counter (n) (unless (zerop n) (print (counter (1- n))))))
(counter 100000))
NIL
没错；没有什么！ (counter (1- n)) 永远不会 returns，所以 print 永远不会被调用。
从尾部位置调用自身的递归函数会导致堆栈溢出；语言实现必须支持某种形式的 tail call elimination 才能避免此问题。
I've been avoiding using loops to make lisp style code.
Common Lisp 不要求实现执行尾调用消除，但 Scheme 实现必须这样做。在 Scheme 中，使用递归进行迭代是惯用的，但在 Common Lisp 中，使用其他迭代设备是惯用的，除非递归为手头的问题提供了自然的解决方案。
虽然 Common Lisp 实现不需要进行尾调用消除，但很多实现都需要。 Clisp 确实支持有限的尾调用消除，但仅限于编译后的代码，并且仅适用于自递归尾调用。这没有很好的记录，但是 there is some discussion to be found here 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)。
如前所述，惯用的 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>