Lisp中出现‘Stack overflow (deep)’错误，素因数递归函数排查

咱们来一步步拆解你遇到的栈溢出问题，顺便把代码逻辑理顺：

导致栈溢出的核心原因 #

你的代码里有两个关键问题直接引发了栈溢出，还有一些逻辑漏洞需要修复：

1. is-prime函数递归效率极低
   你当前的is-prime是从n-1开始逐个向下递归检查，比如检查1000的素性，要递归999次，稍大的数直接就把调用栈撑爆了。而且这里还有逻辑错误：当输入n=1时返回的是空列表()，但1不是素数，应该返回nil。

2. prime-factors-helper代码不完整且逻辑有问题
   你写的(+ 1...)是未完成的代码，而且递归时如果找到因数就直接+1的话，会漏掉重复的素因数（比如12的2会只被分解一次），甚至可能陷入无限递归，进一步加剧栈溢出。另外，判断(< n (/ x 2))是多余的，只要n能整除x且是素数，就可以作为因数。

修复后的完整代码 #

先给你修复好的可运行版本，再逐个解释改进点：

;; 优化的素数判断函数
(defun is-prime (n)
  (cond
    ((<= n 1) nil)          ; 1及以下不是素数
    ((= n 2) t)             ; 2是素数
    ((evenp n) nil)         ; 偶数直接排除（除了2）
    (t (is-prime-helper n 3)))) ; 从3开始检查奇数因数

;; 素数判断的辅助函数，只检查到sqrt(n)，步长2
(defun is-prime-helper (n d)
  (if (> (* d d) n)
      t
      (if (zerop (rem n d))
          nil
          (is-prime-helper n (+ d 2)))))

;; 素因数分解主函数
(defun prime-factors (x)
  (prime-factors-helper x 2))

;; 素因数分解辅助函数
(defun prime-factors-helper (x n)
  (cond
    ((= x 1) nil)           ; 分解完成
    ((is-prime x) (list x)) ; x本身是素数，直接返回
    ((zerop (rem x n))      ; 如果n是x的因数
     (cons n (prime-factors-helper (/ x n) n))) ; 保留n，继续分解x/n（重复因数也能处理）
    (t (prime-factors-helper x (if (= n 2) 3 (+ n 2)))))) ; 找不到因数就尝试下一个数（偶数跳过）

关键改进点说明 #

1. is-prime的优化

   • 先处理边界情况：直接排除<=1的数、2单独判断、偶数直接返回nil，减少不必要的递归。
   • 辅助函数is-prime-helper只检查到sqrt(n)（因为如果n有因数，必有一个不大于sqrt(n)），而且步长是2（只检查奇数），递归深度大幅降低，完全不会栈溢出。

2. prime-factors-helper的逻辑修复

   • 当找到一个素因数n时，递归处理(/ x n)但保持n不变，这样能处理重复因数（比如18=233）。
   • 找不到因数时，跳过偶数（n=2之后直接跳到3，之后每次+2），减少无效检查。
   • 增加了(= x 1)的终止条件，确保分解到1时停止递归。

测试示例 #

运行一下看看效果：

(prime-factors 12) ; 返回 (2 2 3)
(prime-factors 100) ; 返回 (2 2 5 5)
(prime-factors 13) ; 返回 (13)
(prime-factors 1) ; 返回 nil

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