如何分析给定两个Lisp函数的时间与空间复杂度？

咱们先从最清晰的fatt函数开始拆解，再聊那个带累加器的fact——先提一句，你给出的fact代码里有两个明显的笔误：一是递归调用里的(- 1 x)应该是(- x 1)（不然x>1时会得到负数，递归永远停不下来）；二是调用的fatt应该是fact自己（因为fatt只接受一个参数，传两个参数会直接报错）。我会先基于修正后的正确代码分析，再提原错误代码的问题。

1. fatt：普通递归版阶乘 #

先看代码：

(defun fatt (x)
  (if (zerop x)
      1
      (* x (fatt (- x 1)))))

时间复杂度 #

这个函数的逻辑是，每次递归把输入x减1，直到x等于0才触发终止条件。对于输入n，总共会执行n+1次函数调用（从x=n一直到x=0）。每次调用里的操作——判断zerop、乘法运算——都是常数时间（O(1)）。所以总的时间复杂度是O(n)，和输入的大小线性相关。

空间复杂度 #

普通递归会依赖调用栈来保存每一层的上下文：每调用一次fatt，都会在栈上保存当前的x值和返回地址，直到递归到base case（x=0）才开始回溯。栈的深度等于递归的次数，也就是n+1层。所以空间复杂度是O(n)，和输入大小线性相关。

2. fact：带累加器的尾递归版本（修正后） #

修正后的正确代码应该是这样的：

(defun fact (x &optional (acc 1))
  (if (zerop x)
      acc
      (fact (- x 1) (* x acc))))

时间复杂度 #

和普通递归版一样，这个函数也需要执行n+1次调用，每次调用的操作都是常数时间。所以时间复杂度还是O(n)——尾递归并没有优化时间，它的优势在空间上。

空间复杂度 #

这里的关键是尾递归优化（TCO）：

• 如果你的Lisp实现（比如SBCL、CLISP等）支持TCO，那么编译器/解释器会把尾递归转换成循环结构，不需要为每一次递归调用创建新的栈帧——只需要更新x和acc两个变量的值就行。这种情况下，空间复杂度是O(1)（常数空间）。
• 如果你的Lisp实现不支持TCO，那么这个函数的行为和普通递归一样，每一次调用都会占用栈帧，空间复杂度还是O(n)。

关于你原代码的说明 #

你给出的fact函数里，递归调用(fatt (- 1 x) (* x acc))是无法运行的：一方面(- 1 x)会产生负数导致递归无法终止，另一方面fatt只接受一个参数，传两个参数会直接抛出错误。所以这应该是输入时的笔误，上面的分析基于合理修正后的代码。

内容的提问来源于stack exchange，提问作者Giuseppe Giubaldo