Lisp递归函数判断非重复平方和的执行过程解析及优化问询

原函数代码 #

(defun sum-of-squares-p (n)
  (labels ((helper (i sum)
             (cond ((= sum n) t)
                   ((> sum n) nil)
                   ((> (* i i) n) nil)
                   (t (or (helper (+ i 1) (+ sum (* i i)))
                          (helper (+ i 1) sum))))))
    (if (= n 0)
        t
        (helper 1 0))))

这个函数用来判断数字n是否能表示为不重复平方数的和，核心是内部的helper递归函数：

• i：当前尝试的平方数的底数（从1开始递增）
• sum：当前已经累加的平方和

helper的逻辑通过四个分支覆盖所有情况：

1. 若当前累加和sum等于目标n，说明找到有效组合，返回t
2. 若sum超过n，这条路走不通，返回nil
3. 若当前i的平方已经大于n，后续更大的数平方只会更大，不可能凑出目标，返回nil
4. 否则分两种递归尝试：
   • 选当前i的平方：把i²加到sum里，i加1继续尝试
   • 不选当前i的平方：sum不变，i加1继续尝试
     只要其中一条路径返回t，整个or表达式就返回t

以(sum-of-squares-p 10)为例的完整执行流程 #

你之前梳理到第4步(helper 4 14)返回nil，后续完整流程如下：

1. 回到上一层的or表达式：(or (helper 4 14) (helper 4 5))，第一个分支返回nil，因此执行第二个分支(helper 4 5)
2. (helper 4 5)中，(* 4 4)=16>10，触发第三个条件返回nil
3. 此时(helper 3 5)的两个分支都返回nil，所以(helper 3 5)返回nil，回到上一层(helper 2 1)的or表达式：(or (helper 3 5) (helper 3 1))
4. 执行第二个分支(helper 3 1)：
   • i=3，(*3 3)=9，sum+9=1+9=10，等于目标n，触发第一个条件返回t
5. 这个t向上传递，整个or表达式返回t，最终(sum-of-squares-p 10)返回t

更简洁的实现方式 #

可以把逻辑拆分成语义更清晰的函数，或者用迭代方式模拟递归：

拆分函数版本 #

;; 判断x是否是平方数（可选扩展函数）
(defun square-p (x)
  (let ((root (isqrt x)))
    (= (* root root) x)))

;; 核心递归：从start开始的不重复平方数，能否凑出剩余值remaining
(defun can-sum-squares (remaining start)
  (cond ((= remaining 0) t)
        ((< remaining 0) nil)
        ((> (* start start) remaining) nil)
        (t (or (can-sum-squares (- remaining (* start start)) (+ start 1))
               (can-sum-squares remaining (+ start 1))))))

(defun sum-of-squares-p (n)
  (if (= n 0)
      t
      (can-sum-squares n 1)))

这个版本把原函数的helper拆成独立的can-sum-squares，每个函数只负责单一逻辑，可读性更强。

迭代版本（用栈模拟递归） #

如果想避免递归，用栈保存需要尝试的状态：

(defun sum-of-squares-p (n)
  (if (= n 0)
      t
      (let ((stack (list (cons 1 n))))
        (loop while stack do
              (destructuring-bind (start . remaining) (pop stack)
                (cond ((= remaining 0) (return t))
                      ((< remaining 0) nil)
                      ((> (* start start) remaining) nil)
                      (t (push (cons (+ start 1) remaining) stack)
                         (push (cons (+ start 1) (- remaining (* start start))) stack))))
              finally (return nil)))))

这个版本用栈存储每一步需要尝试的两种状态（选当前平方数/不选），弹出栈顶元素处理，直到找到符合条件的情况或栈为空。

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