Lisp中的"堆栈溢出(深层)"错误

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)" 

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

[UPDATE]

我重新定义了这个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比较的数字,然后你可以重写if使用表达式逻辑表达式or,and和not.

(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 >