recursion - 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)
• 原子所以返回 1
• 原子数 ((2 3))
• 不为空
• 不是原子
• 原子数 (2)
• 返回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
*