lisp - Lisp 中的 "Stack overflow (deep)"错误

Question

我正在尝试创建一个函数 prime-factors 来返回数字的质因数。为此，我创建了 is-prime 函数和 prime-factors-helper 来对素因子进行递归检查。

(defun is-prime (n &optional (d (- n 1))) 
  (if (/= n 1) (or (= d 1)
          (and (/= (rem n d) 0)
               (is-prime  n (- d 1)))) ()))

(defun prime-factors-helper (x n)
   (if (is-prime x) (list x) 
        (if (is-prime n) 
            (if (AND (= (mod x n) 0) (< n (/ x 2)))
                (append (list n) (prime-factors-helper (/ x n) (+ 1 n)))
                (prime-factors-helper x (+ 1 n)))       
            (prime-factors-helper x (+ 1 n)))))

(defun prime-factors (x)
    (prime-factors-helper x 2)) 

prime-factors 的主要功能似乎适用于某些数字。然而，对于大数，它返回 "Stack overflow (deep)"。

CL-USER 44 : 5 > (prime-factors 66)
(2 3 11)

CL-USER 49 : 5 > (prime-factors 512)
"Stack overflow (deep)" 

你能告诉我为什么会返回这个错误吗？递归调用有问题吗？

[更新]

我重新定义了 is-prime 函数，但显然这不是问题所在。

(defun is-prime (x &optional (i 2))
    (if (= x 1) nil
        (if (or (= x 2) (= x 3)) t
            (if (<= i (sqrt x))
                (if (= (mod x i ) 0) nil
                    (is-prime x (+ i 1)))
                t))))



(defun prime-factors-helper (x n)
   (if (is-prime x) 
       (list x) 
       (if (is-prime n) 
            (if (AND (= (mod x n) 0) (<= n (/ x 2)))
                (cons n (prime-factors-helper (/ x n) n))
                (prime-factors-helper x (+ 1 n)))       
            (prime-factors-helper x (+ 1 n)))))

优化问题

我还有另一个优化问题。当我有一个大数字时，例如 123456789，我收到此错误消息 Stack overflow (stack size 261120)。我相信因为正确的答案是 (3 3 3607 3803)，我的程序一旦用前两个元素 (3 3) 构造列表，它就会这样长期寻找下一个质因数。如何优化我的代码？

Answer 1

关于您的代码的一些一般性说明:

(defun is-prime (x &optional (i 2))
    (if (= x 1) nil
        (if (or (= x 2) (= x 3)) t
            (if (<= i (sqrt x))
                (if (= (mod x i ) 0) nil
                    (is-prime x (+ i 1)))
                t))))

(defun prime-factors-helper (x n)
   (if (is-prime x) (list x) 
        (if (is-prime n) 
            (if (and (= (mod x n) 0) (<= n (/ x 2)))
                (append (list n) (prime-factors-helper (/ x n) (+ 1 n)))
                (prime-factors-helper x (+ 1 n)))       
            (prime-factors-helper x (+ 1 n)))))


(defun prime-factors (x)
    (prime-factors-helper x 2)) 

CL-USER 44 : 5 > (prime-factors 66)
(2 3 11)

您应该改进的几件事:缩进、代码格式、正确使用 REPL 和 Lisp 函数的选择:

代码缩进和格式化

让我们从缩进和格式开始。通常的缩进是:

(defun is-prime (x &optional (i 2))
  (if (= x 1)
      nil
    (if (or (= x 2) (= x 3))
        t
      (if (<= i (sqrt x))
          (if (= (mod x i ) 0)
              nil
            (is-prime x (+ i 1)))
        t))))

(defun prime-factors-helper (x n)
  (if (is-prime x)
      (list x) 
    (if (is-prime n) 
        (if (and (= (mod x n) 0) (<= n (/ x 2)))
            (append (list n) (prime-factors-helper (/ x n) (+ 1 n)))
          (prime-factors-helper x (+ 1 n)))
      (prime-factors-helper x (+ 1 n)))))


(defun prime-factors (x)
  (prime-factors-helper x 2)) 

改进代码

现在我们可以重写前两个函数:

使用case 比较数字，然后您可以使用or、and< 将if 表达式重写为逻辑表达式 而 不是 。

(defun is-prime (x &optional (i 2))
  (case x
    (1     nil)
    ((2 3) t)
    (t     (or (not (<= i (sqrt x)))
               (and (/= (mod x i) 0)
                    (is-prime x (+ i 1)))))))

接下来我们使用 cond 减少缩进级别。

(append (list foo) bar) 只是 (cons foo bar)。

我们也可以去掉一个if。

(defun prime-factors-helper (x n)
  (cond ((is-prime x)
         (list x))
        ((and (is-prime n)
              (= (mod x n) 0)
              (<= n (/ x 2)))
         (cons n (prime-factors-helper (/ x n) (+ 1 n))))
        (t (prime-factors-helper x (+ 1 n)))))

测试函数

现在我们需要测试一下:

(defun test (&optional (n 20))
  (loop for i from 2 below n
        for factors = (prime-factors i)
        do (print (list i
                        (= (reduce #'* factors) i)
                        (cons '* factors)))))

有问题:解决!

如您所见，还有一个问题...当我们计算 8 的因数时，我不得不将代码从无限循环中打断。

CL-USER 51 > (test)

(2 T (* 2)) 
(3 T (* 3)) 
(4 T (* 2 2)) 
(5 T (* 5)) 
(6 T (* 2 3)) 
(7 T (* 7)) 
Break.
  1 (continue) Return from break.
  2 (abort) Return to top loop level 0.

但是那个很容易修复，留作练习。

REPL。

当你在 LispWorks 中有这样的提示时

CL-USER 44 : 5 > 

这意味着您的休息深度为五(!)级。

输入 :top 命令进入顶级 repl 的时间:

CL-USER 44 : 5 > :top

CL-USER 45 >