需要解释 Lisp 函数检查数字是否为非重复平方和的递归过程

Question

(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 是不相同的平方和，则返回 t。例如：10 = 3^2 + 1^2、9 = 3^2，但是 2 != 1^2 + 1^2，导致相同的数字 (1) 两次。我很难理解这个递归是如何工作的。

例如：(平方和-p 10)...步骤：

1. （助手 1 0）

2. (帮手 2 1)

3. （助手 3 5）

4. (helper 4 14) -> condition ((> sum n ) nil) = 14 > 10, 返回 nil 然后

   or 的第二个表达式叫做 ->

   1. 是又叫like(helper 1 0)，还是叫like(helper 5 5)？

无论如何，我很难理解，这段代码是如何正确地成功 T 或 NIL 的，我需要你的帮助来理解得到结果的过程。

我是 lisp 的新手，我们只学了很少的课程，我们只学了 lisp 中的数学东西，“if”，“cond”，“labels”，“and”，“or”，以及如何编写迭代函数。

你能解释一下这个递归是如何工作的吗？

有没有办法让谓词更简单，也许有两个或更多的功能？

我试着把递归的每一步都写在纸上，但没有得到我的结果。我也试着迭代地写它，但对我没有用。

Answer 1

Common Lisp 提供了一个

trace

宏。 LispWorks 有它的扩展版本，例如可以跟踪子函数。

我们需要定义要跟踪的函数：

CL-USER 38 > (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))))
SUM-OF-SQUARES-P

现在我们需要在 LispWorks 中编译解释函数（因为我们在一个 LispWorks Listener 中定义了它，默认不编译）：

CL-USER 39 > (compile 'sum-of-squares-p)
SUM-OF-SQUARES-P
NIL
NIL

现在我们可以跟踪

helper

函数，它由

labels

函数内部的

sum-of-squares-p

结构定义。

CL-USER 40 > (trace (labels helper sum-of-squares-p))
((SUBFUNCTION (LABELS HELPER) SUM-OF-SQUARES-P))

调用函数

sum-of-squares-p

现在将生成以下跟踪输出：

CL-USER 41 > (sum-of-squares-p 10)
0 (SUBFUNCTION (LABELS HELPER) SUM-OF-SQUARES-P) > ...
  >> I   : 1
  >> SUM : 0
  1 (SUBFUNCTION (LABELS HELPER) SUM-OF-SQUARES-P) > ...
    >> I   : 2
    >> SUM : 1
    2 (SUBFUNCTION (LABELS HELPER) SUM-OF-SQUARES-P) > ...
      >> I   : 3
      >> SUM : 5
      3 (SUBFUNCTION (LABELS HELPER) SUM-OF-SQUARES-P) > ...
        >> I   : 4
        >> SUM : 14
      3 (SUBFUNCTION (LABELS HELPER) SUM-OF-SQUARES-P) < ...
        << VALUE-0 : NIL
      3 (SUBFUNCTION (LABELS HELPER) SUM-OF-SQUARES-P) > ...
        >> I   : 4
        >> SUM : 5
      3 (SUBFUNCTION (LABELS HELPER) SUM-OF-SQUARES-P) < ...
        << VALUE-0 : NIL
    2 (SUBFUNCTION (LABELS HELPER) SUM-OF-SQUARES-P) < ...
      << VALUE-0 : NIL
    2 (SUBFUNCTION (LABELS HELPER) SUM-OF-SQUARES-P) > ...
      >> I   : 3
      >> SUM : 1
      3 (SUBFUNCTION (LABELS HELPER) SUM-OF-SQUARES-P) > ...
        >> I   : 4
        >> SUM : 10
      3 (SUBFUNCTION (LABELS HELPER) SUM-OF-SQUARES-P) < ...
        << VALUE-0 : T
    2 (SUBFUNCTION (LABELS HELPER) SUM-OF-SQUARES-P) < ...
      << VALUE-0 : T
  1 (SUBFUNCTION (LABELS HELPER) SUM-OF-SQUARES-P) < ...
    << VALUE-0 : T
0 (SUBFUNCTION (LABELS HELPER) SUM-OF-SQUARES-P) < ...
  << VALUE-0 : T
T