Lisp 递归函数在第一次调用时缺少基本情况

Question

我昨天开始用 lisp 编程，所以如果我犯了一些真正的新手错误，请原谅。我正在尝试创建一个使用钟形三角形计算铃号的函数，但我的递归三角形函数无法正常工作。我也确定如果我的递归三角函数工作，我的递归钟函数也会以某种方式被破坏。

当我测试三角函数时，我得到了输出：

(defun bell(l n)
    (if(< n 1)(list 1))
    (if (= n 1)(last l))
    (bell (triangle (reverse l) (last l) (list-length l)) (- n 1))
)
(defun triangle(pL nL i)
    (if(<= i 0)
        (write "equals zero!")
        (reverse nL)
    )
    (triangle pL (append (list (+ (nth i pL) (nth i nL))) nL) (- i 1))  
)
(write (triangle '(1) '(1) 0))


=>


"equals zero!""equals zero!"
*** - NTH: -1 is not a non-negative integer

出于某种原因，它打印了我的调试代码两次，即使该函数在第一次调用时应该符合我的基本情况。

Answer 1

您的 if 没有任何效果。它们经过评估并产生结果，但随后您将它们丢弃。就像

(defun abc ()
  'a
  'b
  'c)

将评估 'a 和 'b 以生成符号 a 和 b，然后计算 'c 以产生符号 c，然后是 return编辑。在

的情况下

(if(<= i 0)
        (write "equals zero!")  ; then 
        (reverse nL)            ; else
    )

你正在比较 i 是否小于或等于零，如果是，你打印等于零，如果不是，你（非破坏性地）反转 nL 并丢弃结果。然后通过调用 triangle 来完成该函数。看起来你可能想要 return 当 i 小于或等于零时反转 nL。请改用 cond，因为您可以有多种主体形式，如：

(cond
  ((<= i 0) (write ...) (reverse nL))
  (t (triangle ...)))

您还可以使用 if 和 progn 对表格进行分组：

(if (<= i 0) 
  (progn 
    (write ...)
    (reverse nL))
  (triangle ...))

你的其他函数也有同样的问题。如果您想在第一种情况下 return 值，则需要使用实际上 returns 它们的形式。例如：

(if (< n 1)
    (list 1)
    (if (= n 1)
        (last l)
        (bell #| ... |#)))

更惯用的是 cond，并使用 list 而不是 l，看起来很像 1:

(cond
  ((< n 1) (list 1))
  ((= n 1) (last list))
  (t (bell #| ... |#)))

Answer 2

For some reason, it is printing my debug code twice even though the function should be meeting my base case on the first call.

它被打印了两次，因为 if 没有按照您的想法去做。第一个 if 测试为真，因此 equals zero! 被打印出来。之后，调用三角函数的递归调用。测试再次为真 (-1 <= 0)，因此 equals zero! 再次打印。最后，你会得到一个错误，因为 nthcdr 函数是用 -1 调用的。我强烈推荐你一个好的 lisp 调试器。 Lispworks的那个不错

老实说，我不明白你试图用你的代码实现什么的逻辑。所以我写了我的：

(defun generate-level (l &optional (result))
  "given a list l that represents a triangle level, it generates the next level"
  (if (null l) result
    (if (null result)
        (generate-level l (list (car (last l))))
      (generate-level (cdr l) (append result 
                                      (list (+ (car l) 
                                               (car (last result)))))))))


(defun bell (levels &optional (l))
  "generate a bell triangle with the number of labels given by the first parameter"
  (unless (zerop levels)
        (let ((to-print (if (null l) (list 1) (generate-level l))))
          (print to-print)
          (bell (1- levels) to-print))))

要了解实现的事情：

&optional (parameter)：该参数可选，默认为nil。
append 连接两个列表。我用它来插入列表的后面。
let ((to-print x)) 创建一个名为 to-print 的新变量绑定（局部变量）并初始化为 x.
我差点忘了提到 if 在 common lisp 中是如何工作的： (if (= x 1) y z) 表示如果 x 等于 1 那么 return y，否则 z。

现在如果调用函数创建一个 7 级的钟形三角形：

CL-USER 9 > (bell 7)

(1) 
(1 2) 
(2 3 5) 
(5 7 10 15) 
(15 20 27 37 52) 
(52 67 87 114 151 203) 
(203 255 322 409 523 674 877) 
NIL

用适当的填充打印它会更好，像这样：

                    1
                 1     2
              2     3     5
           5     7    10    15
       15    20    27    37    52
    52    67    87   114   151   203
203   255   322   409   523   674   877

但我把它作为练习留给 reader。

Answer 3

谢谢大家的解释。我最终到达了下面的代码。我意识到 if 块的工作方式类似于..

(if (condition) (execute statement) (else execute this statement))

(defun bell(l n)
    (if (< n 2)(last l)
        (bell (triangle l (last l) 0) (- n 1))
    )
)
(defun triangle(pL nL i)
    (if(= i (list-length pL)) nL
        (triangle pL (append  nL (list (+ (nth  i pL) (nth i nL)))) (+ i 1))
    )  
)
(write (bell (list 1) 10))

Lisp 递归函数在第一次调用时缺少基本情况

Lisp recursive function missing base case on first call

lisp

recursion

common-lisp