递归函数在 Lisp 中是如何工作的？

Question

所以我用 Lisp 编写代码，我想出了一个函数来计算列表（没有子列表）中的原子数。所以代码是这样的：

(defun num-atoms (list)
  (cond
    ((null list) 0)
    ((atom list) 1)
    (t (+ (num-atoms (car list))
          (num-atoms (cdr list))))))

这对我来说很有效并且很有意义。因此，如果我在参数中使用列表 (1 2 3) 调用此函数，它应该如下所示：

(原子数'(1 2 3))
不为空
不是原子
原子数(1)
atom 所以 returns 1
原子数 ((2 3))
不为空
不是原子
原子数 (2)
return 1
.....
等等

但是，如果我这样写代码：

(defun num-atoms (list)
  (cond
    ((null list) 0)
    ((atom list) 1)
    (t (+ (num-atoms (cdr list))
          (num-atoms (car list))))))

这里我只是在最后一行调换了de car和cdr的位置。

它仍然有效！如果我做一个跟踪，它会给我相同顺序的原子数！它首先计算 '(1 2 3) 列表中的 1，依此类推。有人可以向我解释代码的第二个版本如何仍然有效吗？我不太明白这里的逻辑。

Answer 1

如果您 trace 这两个函数，您会发现它们有何不同。

在您的第一个版本中，原子按顺序处理，因为该函数处理第一个元素 (car)，然后处理其余元素 (cdr)。

在第二个版本中，原子以相反的顺序进行处理，因为函数在处理第一个元素之前先处理剩余的元素。所以找到的第一个原子是列表中的最后一个，然后堆栈展开。

当然，两种情况下的结果是相同的，因为加法是 commutative。

* (defun num-atoms(list)
  (cond
   ((null list) 0)
   ((atom list) 1)
   (t (+ (num-atoms (car list)) (num-atoms (cdr list))))))

NUM-ATOMS
* (trace num-atoms)

(NUM-ATOMS)
* (num-atoms '(1 2 3))
  0: (NUM-ATOMS (1 2 3))
    1: (NUM-ATOMS 1)
    1: NUM-ATOMS returned 1
    1: (NUM-ATOMS (2 3))
      2: (NUM-ATOMS 2)
      2: NUM-ATOMS returned 1
      2: (NUM-ATOMS (3))
        3: (NUM-ATOMS 3)
        3: NUM-ATOMS returned 1
        3: (NUM-ATOMS NIL)
        3: NUM-ATOMS returned 0
      2: NUM-ATOMS returned 1
    1: NUM-ATOMS returned 2
  0: NUM-ATOMS returned 3
3

和

* (defun num-atoms(list)
  (cond
   ((null list) 0)
   ((atom list) 1)
   (t (+ (num-atoms (cdr list)) (num-atoms (car list))))))

NUM-ATOMS
* (num-atoms '(1 2 3))
  0: (NUM-ATOMS (1 2 3))
    1: (NUM-ATOMS (2 3))
      2: (NUM-ATOMS (3))
        3: (NUM-ATOMS NIL)
        3: NUM-ATOMS returned 0
        3: (NUM-ATOMS 3)
        3: NUM-ATOMS returned 1
      2: NUM-ATOMS returned 1
      2: (NUM-ATOMS 2)
      2: NUM-ATOMS returned 1
    1: NUM-ATOMS returned 2
    1: (NUM-ATOMS 1)
    1: NUM-ATOMS returned 1
  0: NUM-ATOMS returned 3
3
*

递归函数在 Lisp 中是如何工作的？

How do recursive functions work in Lisp?

lisp

recursion

common-lisp